# Performance Optimization of Object Tracking Algorithms in OpenCV on GPUs
## 2 Background and Motivation
### GPU Occupancy  
_Occupancy_ is one of the metrics to measure the GPU's computing resource utilization. From the kernel's perspective, resource utilization corresponds to the number of active wavefronts. Therefore, occupancy refers to the theoretical maximum percentage of wavefronts that can be activated simultaneously in a CU. As described in Section 2.2, each CU can execute 40 wavefronts simultaneously, and a 50% occupancy means 20 wavefronts are activated simultaneously in the CU. High occupancy generally shows high throughput  
Figure 3: Architecture of AMD graphics core next.  
in GPU computation since the more active wavefronts, the higher memory latency can be hidden, thereby reducing the stall cycles of SIMD units.  
The occupancy can be limited when the kernel's particular resource usage is large because the available resources are limited in a GPU. The following factors limit the occupancy:  
* The number of _vector general purpose registers (VGPRs)_ and _scalar general purpose registers (SGPRs)_ required by each work-item;
* The work-group size (or the number of work-items in a work-group);
* The amount of LDS memory used by each work-group.  
An SIMD vector unit has a finite number of VGPRs (256 in our tested GPUs). This limits not only the number of VGPRs a wavefront (or a work-item) can use, but also the number of wavefronts that can be activated simultaneously in a CU [19]. The number of active wavefronts equals dividing the total number of VGPRs by the number of VGPRs used in a kernel [19]. For example, a kernel that uses 67 VGPRs can run with three (256/67) active wavefronts. At most 10 wavefronts can be active if each work-item (i.e., a kernel) uses no more than 25 VGPRs. If a kernel uses more than 128 VGPRs, only one wavefront can be active. Table 1 shows the number of active wavefronts by the usage number of VGPRs in the kernel, measured in our environment.  
SGPRs can also limit the number of active wavefronts, but it hardly happens because the use of scalar values is not significant in typical image processing workloads. In our analysis, we found that SGPR was not a major contributor to limiting active wavefronts; this will be described in Section 2.4.  
The number of active wavefronts is also limited by the size of a work-group. A CU can activate up to eight work-groups simultaneously [19]. The CU scheduler fetches wavefronts from the activated work-groups and schedules them to the SIMD vector units. Hence, if the size of a work-group is too small, a CU cannot activate the maximum number of wavefronts. For example, if one work-group is activated and the group has 256 work-items, each SIMD unit has only one active wavefront (64 work-items). Hence, the occupancy becomes only 10%. Hence, it is necessary to have a sufficient work-group size so that a CU can find a sufficient number of wavefronts to schedule.  
The number of work-groups that can be activated is limited by the size of LDS memory usage per work-group. Whenever a work-group is activated in a CU, its local memory is allocated from the LDS memory. Hence, if the LDS memory is full, no more work-groups can be activated until a work-group completes. Therefore, the amount of local memory used by a work-group limits the number of activated work-groups in a CU. As mentioned above, the occupancy can be limited when a few work-groups are scheduled and each work-group has a few work-items. Hence, if LDS memory usage is high, only a few work-groups can be activated, thereby increasing the possibility of low occupancy.