Description
Priority queues are among the most fundamental building blocks for scheduling work and are an integral part of operating systems, hardware modules and most software projects with time-cricital applications. As can be gleaned from modern API descriptions, work queues are e.g. used internally to schedule tasks that are submitted for processing to the GPU. However, the built-in scheduling system is very limited, and there is little that a programmer can do to influence its behavior to dynamically promote or prioritze urgent computations. Whether it is for virtual reality rendering, geometry subdivision or sampling algorithms, almost any application can be broken into parts that are more important and others that are less so. Software frameworks for priority queuing on the GPU have been shown to enable such adaptive behavior and make the most of available runtime / compute resources.
Based on existing previous work, we want to create a state-of-the-art dynamic priority queuing algorithm for the GPU. In contrast to what has been done before, this particular, new approach should enable the user to define arbitrary, continuous priority ranges for individual parts of a program. A schedule-and-update mechanism will then make sure that important tasks are processed earlier than less important ones to exploit available resources and runtime budgets in time-critical applications. Doing so will enable interesting applications such as adaptive, priority-based path tracing on the GPU:
Tasks
Based on an existing queuing algorithm, the student will have to make sure they provide a state-of-the-art CUDA implementation. As a reference, hierarchical bucket queuing should be implemented on top of it to achieve adaptive behavior Following the suggestions of the supervisor, they should modify the bucket queuing approach to obtain dynamic prioritization behavior. The benefits of this new approach should be documented and thoroughly evaluated. The new approach should be demonstrated in a few useful circumstances, e.g. path tracing, subdivision or foveated rendering.
Requirements
- Interested in algorithms and applications
- Interested in GPU programming and optimization
- Knowledge of C++ and CUDA
- Solid understanding of template-based programming
- More knowledge is always advantageous
Environment
The project should be implemented to produce meaningful evaluation results. Measuring, comparing and documenting the benefits and downsides of the dynamic prioritization method. Statements should be supported by experiments and their results. To deliver on this, you should also try to replicate existing alternative methods from available source code and scientific publications, so you have something meaningful to compare against.
This project is a research topic. For those who are interested, we intend to send obtained results (and you) to a scientific conference for publication.