Abstract CAVLC (Context-Adaptive Variable Length Coding) is a high-performance entropy method for video and image compression. It is the most commonly used entropy method in the video standard H.264. In recent years, several hardware accelerators for CAVLC have been designed. In contrast, high-performance software implementations of CAVLC (e.g., GPU-based) are scarce. A high-performance GPU-based implementation of CAVLC is desirable in several scenarios. On the one hand, it can be exploited as the entropy component in GPU-based H.264 encoders, which are a very suitable solution when GPU built-in H.264 hardware encoders lack certain necessary functionality, such as data encryption and information hiding. On the other hand, a GPU-based implementation of CAVLC can be reused in a wide variety of GPU-based compression systems for encoding images and videos in formats other than H.264, such as medical images. This is not possible with hardware implementations of CAVLC, as they are non-separable components of hardware H.264 encoders. In this paper, we present CAVLCU, an efficient implementation of CAVLC on GPU, which is based on four key ideas. First, we use only one kernel to avoid the long latency global memory accesses required to transmit intermediate results among different kernels, and the costly launches and terminations of additional kernels. Second, we apply an efficient synchronization mechanism for thread-blocks (In this paper, to prevent confusion, a block of pixels of a frame will be referred to as simply block and a GPU thread block as thread-block.) that process adjacent frame regions (in horizontal and vertical dimensions) to share results in global memory space. Third, we exploit fully the available global memory bandwidth by using vectorized loads to move directly the quantized transform coefficients to registers. Fourth, we use register tiling to implement the zigzag sorting, thus obtaining high instruction-level parallelism. An exhaustive experimental evaluation showed that our approach is between 2.5 $$\times$$ × and 5.4 $$\times$$ × faster than the only state-of-the-art GPU-based implementation of CAVLC.

Summary Concurrent execution of tasks in GPUs can reduce the computation time of a workload by overlapping data transfer and execution commands. However, it is difficult to implement an efficient runtime scheduler that minimizes the workload makespan as many execution orderings should be evaluated. In this paper, we employ scheduling theory to build a model that takes into account the device capabilities, workload characteristics, constraints, and objective functions. In our model, GPU tasks scheduling is reformulated as a flow shop scheduling problem, which allow us to apply and compare well‐known heuristics already developed in the operations research field. In addition, we develop a new heuristic, specifically focused on executing GPU commands, that achieves better scheduling results than previous ones. It leverages on a precise GPU command execution model for both computation and data transfers to carry out more advantageous scheduling decisions. A comprehensive evaluation, showing the suitability and robustness of this new approach, is conducted in three different NVIDIA architectures (Kepler, Maxwell, and Pascal). Results confirm the proposed heuristic achieves the best results in more than 90% of the experiments. Furthermore, a comparison has been made with MPS (Multi‐Process Service), the NVIDIA API that deals with the execution of concurrent tasks, which shows that our solution obtains speed‐ups ranging from 1.15 to 1.20.

Scratchpad memories in GPU architectures are employed as software-controlled caches to increase the effective GPU memory bandwidth. Through the use of well-known optimization techniques, such as privatization and tiling, they are properly exploited. Typically, they are banked memories which are addressed with a$\text{mod}(2^N)$bank indexing scheme. Although their bandwidth is fully exploited for linear memory accesses, their performance is burdened when non-unit strides appear in memory access patterns because they provoke bank conflicts. This paper explores the use of configurablebit-vectorandbitwiseXOR-based hash functions to evenly distribute memory addresses of the access patterns over the memory banks, reducing the number of bank conflicts. An exhaustive, but lightweight, search is used to configure bit-vector hash functions. Bitwise hash functions are configured with heuristics. Hardware and software implementations are carried out. For the hardware approach, the experimental results show 24 percent performance speed-up for 22 benchmarks on GPGPU-Sim, a Fermi-like simulator. Bank conflicts are reduced by 96 percent with bit-vector hash functions, and 97 percent with bitwise hash functions using our proposed Minimum Imbalance Heuristic. The software approach, using bit-vector hash functions, demonstrates 23 percent speed-up and 96 percent bank conflict reduction on a Fermi GPU, and 33 percent speed-up and 99 percent bank conflict reduction on a Kepler GPU.

Matrix transposition is an important algorithmic building block for many numeric algorithms such as FFT. With more and more algebra libraries offloading to GPUs, a high performance in-place transposition becomes necessary. Intuitively, in-place transposition should be a good fit for GPU architectures due to limited available on-board memory capacity and high throughput. However, direct application of CPU in-place transposition algorithms lacks the amount of parallelism and locality required by GPU to achieve good performance. In this paper we present our in-place matrix transposition approach for GPUs that is performed using elementary tile-wise transpositions. We propose low-level optimizations for the elementary transpositions, and find the best performing configurations for them. Then, we compare all sequences of transpositions that achieve full transposition, and detect which is the most favorable for each matrix. We present an heuristic to guide the selection of tile sizes, and compare them to brute-force search. We diagnose the drawback of our approach, and propose a solution using minimal padding. With fast padding and unpadding kernels, the overall throughput is significantly increased. Finally, we compare our method to another recent implementation.

Matrix transposition is an important algorithmic building block for many numeric algorithms such as FFT. It has also been used to convert the storage layout of arrays. With more and more algebra libraries offloaded to GPUs, a high performance in-place transposition becomes necessary. Intuitively, in-place transposition should be a good fit for GPU architectures due to limited available on-board memory capacity and high throughput. However, direct application of CPU in-place transposition algorithms lacks the amount of parallelism and locality required by GPUs to achieve good performance. In this paper we present the first known in-place matrix transposition approach for the GPUs. Our implementation is based on a novel 3-stage transposition algorithm where each stage is performed using an elementary tiled-wise transposition. Additionally, when transposition is done as part of the memory transfer between GPU and host, our staged approach allows hiding transposition overhead by overlap with PCIe transfer. We show that the 3-stage algorithm allows larger tiles and achieves 3X speedup over a traditional 4-stage algorithm, with both algorithms based on our high-performance elementary transpositions on the GPU. We also show our proposed low-level optimizations improve the sustained throughput to more than 20 GB/s. Finally, we propose an asynchronous execution scheme that allows CPU threads to delegate in-place matrix transposition to GPU, achieving a throughput of more than 3.4 GB/s (including data transfers costs), and improving current multithreaded implementations of in-place transposition on CPU.

GPUs are increasingly used as compute accelerators. With a large number of cores executing an even larger number of threads, significant speed-ups can be attained for parallel workloads. Applications that rely on atomic operations, such as histogram and Hough transform, suffer from serialization of threads in case they update the same memory location. Previous work shows that reducing this serialization with software techniques can increase performance by an order of magnitude. We observe, however, that some serialization remains and still slows down these applications. Therefore, this paper proposes to use a hash function in both the addressing of the banks and the locks of the scratchpad memory. To measure the effects of these changes, we first implement a detailed model of atomic operations on scratchpad memory in GPGPU-Sim, and verify its correctness. Second, we test our proposed hardware changes. They result in a speed-up up to 4.9× and 1.8× on implementations utilizing the aforementioned software techniques for histogram and Hough transform applications respectively, with minimum hardware costs.

GPU application implementations using scatter approaches will fall into write contention due to atomic updates of output elements, if these result from more than one input element. Colliding threads will be serialized, seriously harming performance. Dealing with these issues requires a proper understanding of the behavior of the scratchpad or shared memory under conflicting accesses caused by concurrent threads. Thus, this paper presents an exhaustive microbenchmark-based analysis of atomic additions in shared memory that quantifies the impact of access conflicts on latency and throughput. This analysis has led us to discover the lock mechanism that enables atomic updates to shared memory and to propose a performance model to estimate the latency penalties due to collisions by position or bank conflicts. Then, we have derived experiments from this model that show us the way to optimize applications using atomic operations. Position and bank conflicts can be diminished by replication and padding, respectively. The benefits of such techniques are illustrated with the optimization of two widely used voting processes: the centroid updating step in k-means clustering, and histogram calculation.

Human action classification is an important task in computer vision. Bag-of-Words using spatio-temporal features and some classification algorithm is one of the most successful methods in this context. In this work we have studied the effect of reducing the vocabulary size using a video word ranking method. We have used the KTH dataset to obtain a vocabulary with more descriptive words and, at the same time, more compact and efficient. Results for different vocabulary sizes show an improvement of the recognition rate whilst reducing the number of words due to the fact that non-descriptive words are removed.

A precise background detection is required for video surveillance applications in order to detect foreground objects. However, in the presence of cluttered scenes, standard techniques for background segmentation can fail. In this work we present a new technique for foreground detection that is able to detect the correct background in complex scenes. It works grouping neighbour pixels that fulfill some kind of spatial and temporal criteria. Spatial criterion is based on the appearance similarity of neighbour pixels while temporal criterion looks for the best temporal correlation in the whole video sequence. Initially, a set of seed points of the image are selected and both criteria are applied in an alternate way until all the pixels of the image have been visited and their background value has been calculated.

This paper presents a novel framework for logo detection in low quality videos. Our method assumes the logo template is unknown in advance and exploits the property that logotype pixels appearance through several consecutive frames has a lower variance than the others. Segmentation is difficult to accomplish if logo continuity is broken. In this work we propose the use of both edge and appearance continuity to carry out the segmentation. By checking edge continuity, the video is split into sequences with stable content. Later, sequences with similar static content are merged in order to build a longer sequence. Next a Gaussian mixture is used to model the variance of the pixels values in the merged sequences. Finally, a threshold that allows identification of the logo pixels is calculated. The new method is compared with a state-of-the-art method, obtaining better results in both accuracy and false logo rejection.

Logotypes superimposed to broadcasted videos supply important information for semantic video annotation, such as the content creator. In this work a novel logo classification and learning system for TV broadcast videos is presented. Logos are segmented from the video stream but scale change, position shift, clutter and noise makes difficult to classify and to recognize them. Several robust features that use edges and shape information have been selected, and a Bayesian network classifier is used to classify the logos. New logos are recognized as such for the first time they appear and passed to a semi-supervised learning system. The learning process clusters the set of new logos to group different instances of the same new logo. A logo model is obtained for each cluster that must be validated by a human to incorporate them into the classification system. Comprehensive tests with a set of 724 TV logos show the high performance of our classification and learning system.

In this paper a technique for video cataloging based on logo detection is shown. No a priori knowledge about shape or spatial-temporal location of logos is assumed. The method implements a new algorithm for online logo detection based on temporal and spatial segmentation of broadcasted videos. Temporal segmentation identifies constant luminance regions within video frames while spatial segmentation helps to refine previous segmented regions. In a final step, identified logos are searched in a database and classified into candidate or learnt logotypes. Learnt logos can be directly tracked through the video. Candidate logotypes are assigned to a cluster of similar logos. After a promotion process, all the candidate logos belonging to the same cluster are used to create a new learnt logotype.

A new approach to the detection of shapes under global deformations is presented. The algorithm is based in the combination of a generalized Hough transform (GHT) and an universal evolutionary global optimizer (UEGO). This method exploits the invariant characteristics to rotation, scale and displacement of the GHT to detect shapes deformed by a global deformation model, and without an initial positioning of the template. The GHT is used as an objective function for the UEGO, an optimizer that is able to find multiple optima with a low computational cost.