Research Of Fine-grained Real-time Load-aware Allocation Strategy For Heterogeneous Computing Systems

With the advent of the big data era,the growing scale of data and the increasing complexity of data analysis algorithms pose a challenge to the computational power of processors.The emergence of heterogeneous computing brings new possibilities.Many regular applications benefit greatly from heterogeneous systems,however,accelerating irregular programs using heterogeneous systems is still a challenge.Irregular programs are widely found in social network analysis,data mining,N-body problems,and graphical algorithms.The properties of irregular programs are likely to change during execution and are often unpredictable,making it difficult to allocate heterogeneous resources to achieve maximum efficiency.In addition,irregularities in applications may lead to control flow divergence,load imbalance,and inefficiencies in parallel execution.In this thesis,we demonstrate the underutilization of computational resources due to irregularity through an in-depth analysis of irregular applications,and also show that previous coarse-grained workload partitioning schemes don’t accelerate irregular applications well,and a more fine-grained load allocation policy is needed to accelerate irregular applications.To address the problem that irregular applications fail to get the ideal acceleration from heterogeneous computing,we propose a fine-grained workload distribution strategy for accelerating irregular applications on discrete CPU-GPU computing systems.The fine-grained workload distribution strategy is a static data partitioning method that reduce the underutilization of resources due to irregularity by reshaping the workload to achieve performance improvement.At the same time,we propose a real-time load-aware fine-grained workload allocation strategy that performs dynamic workload allocation at runtime.The real-time load-aware fine-grained workload allocation overlaps fine-grained partitioning and kernel execution by processing workload in chunks,collecting the processing speed of computing units at runtime to guide fine-grained partitioning and workload allocations.It achieves both device-level load balance and thread-level load balance without offline analysis or training.We implement the proposed strategies in a real heterogeneous computing platform and perform experiments and analysis.The experimental results show that the proposed fine-grained partitioning method can effectively improve the utilization of GPU and then enhance the performance.Meanwhile,the results show that the real-time load-aware fine-grained workload allocation strategy can reduce the execution time by up to 20% compared to the advanced coarse-grained load balancing scheme.