We prove that there exist graphs with n vertices and at most 2n5/3logn2n^{5/3} \log n edges for which every acyclic orientation has in its transitive closure at least (n2
We prove that there exist graphs with n vertices and at most 2n5/3logn edges for which every acyclic orientation has in its transitive closure at least (n2
Matrix multiplication algorithms for cube connected and perfect shuffle computers are presented. It is shown that in both these models two n×nn×nn \times n matrices can be multiplied in <span class="...
详细信息
Considers the data broadcasting problem for single instruction stream, multiple data stream (SIMD) computers. Two versions of this problem, i.e., random access read (RAR) and random access write (RAW) are considered. ...
详细信息
Considers the data broadcasting problem for single instruction stream, multiple data stream (SIMD) computers. Two versions of this problem, i.e., random access read (RAR) and random access write (RAW) are considered. Efficient data broadcasting algorithms are developed for both cases. For the case of a RAR, the complexity of the algorithm is O(q2n) on a q-dimensional nq PE mesh-connected computer and 0(log2N) on an N PE cube-connected or perfect shuffle computer. For the case of a RAW, the complexity of the algorithm is 0(q2n+dqn) on a q-dimensional MCC and 0(log2N+d log N) on an N PE cube-connected or perfect shuffle computer; d is the maximum number of data items written into any one PE.
An opUmal algorithm to route data in a mesh-connected parallel computer is presented This algorithm can be used to perform any data routing that can be specified by the permutation and complementing of the bits in a P...
详细信息
The computational theory of dynamic programming is examined from the viewpoint of parallel computation. A discussion of various forms of parallelism, the corresponding parallel algorithms, the applicability of the alg...
详细信息
The computational theory of dynamic programming is examined from the viewpoint of parallel computation. A discussion of various forms of parallelism, the corresponding parallel algorithms, the applicability of the algorithms to different types of optimization problems, and their advantages over serial computation is presented. In addition, parallel aspects of various dimensionality reduction techniques such as state increment dynamic programming, successive approximations, and shift vectors are also given.
Tato práce se zabývá technologií OpenCL a jejím využitím pro detekci objektů. První část je zaměřená na popis principů technologie OpenCL a základní teorii ...
详细信息
Tato práce se zabývá technologií OpenCL a jejím využitím pro detekci objektů. První část je zaměřená na popis principů technologie OpenCL a základní teorii o detekci objektů. Následuje kapitola analýzy, kde je navržená metoda zpracování s přihlédnutím na možnosti OpenCL. Další část popisuje samotnou implementaci detekční aplikace a experimentálně vyhodnocuje výkon detektoru. Poslední kapitola shrnuje dosažené výsledky.
Tato práce se zabývá praktickým využitím technologie OpenCL ve společnosti AVG. AVG vidí OpenCL jako jednu z možností, jak ulehčit zátěž procesoru a případně urychlit v&#...
详细信息
Tato práce se zabývá praktickým využitím technologie OpenCL ve společnosti AVG. AVG vidí OpenCL jako jednu z možností, jak ulehčit zátěž procesoru a případně urychlit výpočet některých algoritmů. Velká část práce se zabývá optimalizacemi pro grafické karty AMD a NVIDIA, jakožto současné nejrozšířenější karty. Praktická část popisuje paralelizaci dvou algoritmů dodaných AVG, jejich analýzu z pohledu OpenCL a implementaci. Následně jsou popsány a odůvodněny dosažené výsledky a jsou popsány podmínky, pro které má smysl testované paralelní algoritmy použít v reálném produktu. Jako součást implementace je vytvořena knihovna, která usnadňuje práci při vývoji aplikací pracující s OpenCL.
暂无评论