Dynamic spatial index remapping for optimal aggregate performance

摘要

By mapping leaf nodes of a spatial index to processing elements, efficient distribution of workload in an image processing system may be achieved. In addition, processing elements may use a thread table to redistribute workload from processing elements which are experiencing an increased workload to processing elements which may be idle. Furthermore, the workload experienced by processing elements may be monitored in order to determine if workload is balanced. Periodically the leaf nodes for which processing elements are responsible may be remapped in response to a detected imbalance in workload. By monitoring the workload experienced by the processing elements and remapping leaf nodes to different processing elements in response to unbalanced workload, efficient distribution of workload may be maintained. Efficient distribution of workload may improve the performance of the image processing system.

主权项

1. A method of distributing workload in a ray tracing image processing system configured to perform ray tracing operations to render a two dimensional image from a three dimensional scene using a spatial index having internal nodes and leaf nodes defining bounded volumes of the three dimensional scene, comprising:
dividing the leaf nodes into at least a first group and a second group; assigning, by writing to a thread table, a first processing thread to perform operations to perform ray tracing operations for bounding volumes defined by leaf nodes in the first group; assigning, by writing to the thread table, a second processing thread to perform ray tracing operations for bounding volumes defined by leaf nodes in the second group; monitoring an inbox associated with the first processing thread to determine a workload being experienced by the first processing thread, wherein the inbox is configured to store instances of ray and leaf node information to be processed by the first processing thread; performing a ray tracing operation for a first leaf node contained in the inbox, comprising:
determining that the first leaf node is included in the first group of leaf nodes based on assignment information within the thread table;upon determining that the inbox associated with the first processing thread contains a number of instances of ray and leaf node information that exceeds a predefined threshold number of instances of ray and leaf node information, determining that the second processing thread is currently idle by accessing the thread table to retrieve an idle value corresponding to the second processing thread; and performing the ray tracing operation for the first leaf node using the second processing thread, rather than the first processing thread, based on the retrieved idle value.