Zobrazeno 1 - 10
of 52
pro vyhledávání: '"Sitchinava, Nodari"'
When lexicographically sorting strings, it is not always necessary to inspect all symbols. For example, the lexicographical rank of "europar" amongst the strings "eureka", "eurasia", and "excells" only depends on its so called relevant prefix "euro".
Externí odkaz:
http://arxiv.org/abs/2006.02219
The single-source shortest path (SSSP) problem is a well-studied problem that is used in many applications. In the parallel setting, a work-efficient algorithm that additionally attains $o(n)$ parallel depth has been elusive. Alternatively, various a
Externí odkaz:
http://arxiv.org/abs/1908.09378
The program performance on modern hardware is characterized by \emph{locality of reference}, that is, it is faster to access data that is close in address space to data that has been accessed recently than data in a random location. This is due to ma
Externí odkaz:
http://arxiv.org/abs/1902.07928
Autor:
Afshani, Peyman, Fagerberg, Rolf, Hammer, David, Jacob, Riko, Kostitsyna, Irina, Meyer, Ulrich, Penschuck, Manuel, Sitchinava, Nodari
We initiate a study of algorithms with a focus on the computational complexity of individual elements, and introduce the fragile complexity of comparison-based algorithms as the maximal number of comparisons any individual element takes part in. We g
Externí odkaz:
http://arxiv.org/abs/1901.02857
Autor:
Sitchinava, Nodari, Strash, Darren
Visibility graph reconstruction, which asks us to construct a polygon that has a given visibility graph, is a fundamental problem with unknown complexity (although visibility graph recognition is known to be in PSPACE). We show that two classes of un
Externí odkaz:
http://arxiv.org/abs/1708.09842
Sorting is a primitive operation that is a building block for countless algorithms. As such, it is important to design sorting algorithms that approach peak performance on a range of hardware architectures. Graphics Processing Units (GPUs) are partic
Externí odkaz:
http://arxiv.org/abs/1702.07961
Autor:
Afshani, Peyman, Sitchinava, Nodari
In this paper, we look at the complexity of designing algorithms without any bank conflicts in the shared memory of Graphical Processing Units (GPUs). Given input of size $n$, $w$ processors and $w$ memory banks, we study three fundamental problems:
Externí odkaz:
http://arxiv.org/abs/1507.01391
We study the problem of list ranking in the parallel external memory (PEM) model. We observe an interesting dual nature for the hardness of the problem due to limited information exchange among the processors about the structure of the list, on the o
Externí odkaz:
http://arxiv.org/abs/1406.3279
Thesis (M. Eng.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 2003.
Includes bibliographical references (p. 61-64).
Fast developments in semiconductor industry have led to smaller and cheaper
Includes bibliographical references (p. 61-64).
Fast developments in semiconductor industry have led to smaller and cheaper
Externí odkaz:
http://hdl.handle.net/1721.1/18034
Autor:
Sitchinava, Nodari, Weichert, Volker
In this paper we present a framework for designing algorithms in shared memory of GPUs without incurring memory bank conflicts. Using our framework we develop the first comparison-based shared memory sorting algorithm that incurs no bank conflicts. I
Externí odkaz:
http://arxiv.org/abs/1306.5076