Optimizing data warehousing applications for GPUs using dynamic stream scheduling and dispatch of fused and split kernels
View Patent ↗Systems and methods for managing a processor and one or more co-processors for a database application whose queries have been processed into an intermediate form (IR) containing kernels of the database application that have been fused and split; dynamically scheduling such kernels on CUDA streams and further dynamically dispatching kernels to GPU devices by estimating execution time in order to achieve high performance.
1. A method for managing a processor and one or more co-processors for a database application whose queries have been processed into an intermediate form (IR) containing operators of the database application that have been fused and split and consisting of multiple co-processor kernels, comprising:
dynamically scheduling the fused and split operators to co-processor streams; and
dynamically dispatching the co-processor kernels of the fused and split operators to selected streams;
applying a scheduler to a list of the fused and split operators with relational algebra (RA) in a database query plan, wherein RA operators are used to express the high level semantics of an application in terms of a series of bulk operations on relations and wherein each operator includes kernels that are intercepted and wherein the scheduler first selects the oldest operator and inserts the operator into a scheduling list;
allocating an available co-processor stream from the pool to the operator and adding operators to the scheduling list until the scheduling list is full and thereafter issuing individual co-processor kernels to the co-processor stream.
2. The method of claim 1 , comprising selecting one or more operators based on usage of co-processor resources.
3. The method of claim 1 , comprising selecting one or more operators based on age.
4. The method of claim 1 , comprising selecting the co-processor kernels based on estimated execution time.
5. The method of claim 1 , comprising estimating execution time of database operators using data size and linearity.
6. The method of claim 1 , comprising selecting the co-processor kernels based on actual completion time of corresponding predecessors in their streams.
7. The method of claim 1 , comprising deferring issuance of kernels that transfer data from device to host.
8. The method of claim 1 , comprising removing redundant data transfers by combining back-to-back device-to-host and host-to-device kernels.
9. The method of claim 1 , comprising assigning commands to streams and setting synchronization points without advanced knowledge of a processor stream.
10. The method of claim 1 , comprising executing an application program interface (API).
11. The method of claim 10 , wherein the API includes one or more of the following: a module to get an available stream from a stream pool, a module to assign a command to a predetermined stream, a module to start execution of the stream pool, a module to wait until completion of stream pool execution, a module to assign point-to-point synchronization between a plurality of streams, a module to halt execution of the stream pool.
12. The system of claim 11 where the stream pool consists of a execution time estimation model.
13. The system of claim 12 , where the execution time estimation model is based on a linear interpolation of pool size and execution time.
14. A system for managing a processor and one or more co-processors for a database application whose queries have been processed into an intermediate form (IR) containing operators of the database application that have been fused and split and consisting of multiple co-processor kernels, comprising:
means for dynamically scheduling the fused and split operators to co-processor streams; and
means for dynamically dispatching the co-processor kernels of the fused and split operators to selected streams;
a scheduler to process a list of fused and split operators with relational algebra (RA) in a database query plan, wherein RA operators are used to express the high level semantics of an application in terms of a series of bulk operations on relations and wherein each operator includes kernels that are intercepted and wherein the scheduler first selects the oldest operator and inserts the operator into a scheduling list and wherein the scheduler allocates an available co-processor stream from the pool to the operator and adding operators to the scheduling list until the scheduling list is full and thereafter issuing individual co-processor kernels to the co-processor stream.
15. The system of claim 14 where the stream pool consists of a stream scheduler for scheduling operators and issuing co-processor kernels.
16. The system of claim 11 where the stream pool consists of a performance history table.
17. The system of claim 16 , wherein the performance history table to map a table size and operator to actual execution time.
18. The system of claim 14 , comprising executing an application program interface (API).
19. The system of claim 18 , wherein the API includes one or more of the following: a module to get an available stream from a stream pool, a module to assign a command to a predetermined stream, a module to start execution of the stream pool, a module to wait until completion of stream pool execution, a module to assign point-to-point synchronization between a plurality of streams, a module to halt execution of the stream pool.
20. The system of claim 14 , comprising means for selecting one or more operators based on usage of co-processor resources and means for selecting one or more operators based on age.