We present a parallel visualization algorithm for the illustrative rendering of depth-dependent stylized dense tube data at interactive frame rates. While this computation could be efficiently performed on a GPU device, we target a parallel framework to enable it to be efficiently running on an ordinary multi-core CPU platform which is much more available than GPUs for common users. Our approach is to map the depth information in each tube onto each of the visual dimensions of shape, color, texture, value, and size on the basis of Bertin's semiology theory. The purpose is to enable more legible displays in the dense tube environments. A major contribution of our work is an efficient and effective parallel depthordering algorithm that makes use of the message passing interface (MPI) with VTK. We evaluated our framework with visualizations of depth-stylized tubes derived from 3D diffusion tensor MRI data by comparing its efficiency with several other alternative parallelization platforms running the same computations. As our results show, the parallelization framework we proposed can efficiently render highly dense 3D data sets like the tube data and thus is useful as a complement to parallel visualization environments that rely on GPUs.
Note that the parallel sorting problem @cite_5 @cite_4 , which is at the core of our parallelization framework here, would be easily solved in highly efficient on GPU computing platforms with extensive existing algorithms available @cite_10 @cite_16 . In this paper instead, we target a cheaper solution without relying on high-end computing resources such as GPUs. Alternatively and complementarily, we use CPU-based parallel sorting algorithms leveraging a single processor of multiple cores, which has been almost a bottom-line configuration for modern common computers.
@cite_5 @cite_16 @cite_4 @cite_10
1995596660 2118558147 1992754027 2095890830
This paper presents an algorithm for fast sorting of large lists using modern GPUs. The method achieves high speed by efficiently utilizing the parallelism of the GPU throughout the whole algorithm. Initially, GPU-based bucketsort or quicksort splits the list into enough sublists then to be sorted in parallel using merge-sort. The algorithm is of complexity nlogn, and for lists of 8 M elements and using a single Geforce 8800 GTS-512, it is 2.5 times as fast as the bitonic sort algorithms, with standard complexity of n(logn)^2, which for a long time was considered to be the fastest for GPU sorting. It is 6 times faster than single CPU quicksort, and 10 faster than the recent GPU-based radix sort. Finally, the algorithm is further parallelized to utilize two graphics cards, resulting in yet another 1.8 times speedup. We describe the design of high-performance parallel radix sort and merge sort routines for manycore GPUs, taking advantage of the full programmability offered by CUDA. Our radix sort is the fastest GPU sort and our merge sort is the fastest comparison-based sort reported in the literature. Our radix sort is up to 4 times faster than the graphics-based GPUSort and greater than 2 times faster than other CUDA-based radix sorts. It is also 23 faster, on average, than even a very carefully optimized multicore CPU sorting routine. To achieve this performance, we carefully design our algorithms to expose substantial fine-grained parallelism and decompose the computation into independent tasks that perform minimal global communication. We exploit the high-speed onchip shared memory provided by NVIDIA's GPU architecture and efficient data-parallel primitives, particularly parallel scan. While targeted at GPUs, these algorithms should also be well-suited for other manycore processors. Load balanced parallel radix sort solved the load imbalance problem present in parallel radix sort. By redistributing the keys in each round of radix, each processor has exactly the same number of keys, thereby reducing the overall sorting time. Load balanced radix sort is currently known as the fastest internal sorting method for distributed-memory multiprocessors. However, as the computation time is balanced, the communication time emerges as the bottleneck of the overall sorting performance due to key redistribution. We present in this report a new parallel radix sorter that solves the communication problem of balanced radix sort, called partitioned parallel radix sort. The new method reduces the communication time by eliminating the redistribution steps. The keys are first sorted in a top-down fashion (left-to-right as opposed to right-to-left) by using some most significant bits. Once the keys are localized to each processor, the rest of sorting is confined within each processor, hence eliminating the need for global redistribution of keys. It enables well balanced communication and computation across processors. The proposed method has been implemented in three different distributed-memory platforms, including IBM SP2, Cray T3E, and PC Cluster. Experimental results with various key distributions indicate that partitioned parallel radix sort indeed shows significant improvements over balanced radix sort. IBM SP2 shows 13 to 30 improvement while Cray SGI T3E does 20 to 100 in execution time. PC cluster shows over 2.4-fold improvement in execution time. Sorting is a kernel algorithm for a wide range of applications. We present a new algorithm, GPU-Warpsort, to perform comparison-based parallel sort on Graphics Processing Units (GPUs). It mainly consists of a bitonic sort followed by a merge sort. Our algorithm achieves high performance by efficiently mapping the sorting tasks to GPU architectures. Firstly, we take advantage of the synchronous execution of threads in a warp to eliminate the barriers in bitonic sorting network. We also provide sufficient homogeneous parallel operations for all the threads within a warp to avoid branch divergence. Furthermore, we implement the merge sort efficiently by assigning each warp independent pairs of sequences to be merged and by exploiting totally coalesced global memory accesses to eliminate the bandwidth bottleneck. Our experimental results indicate that GPU-Warpsort works well on different kinds of input distributions, and it achieves up to 30 higher performance than previous optimized comparison-based GPU sorting algorithm on input sequences with millions of elements.