Representing and Scheduling Procedural Generation using Operator Graphs

摘要

In this paper, we present the concept of operator graph scheduling forrnhigh performance procedural generation on the graphics processingrnunit (GPU). The operator graph forms an intermediate representationrnthat describes all possible operations and objects that can arisernduring a specific procedural generation. While previous methodsrnhave focused on parallelizing a specific procedural approach, thernoperator graph is applicable to all procedural generation methodsrnthat can be described by a graph, such as L-systems, shape grammars,rnor stack based generation methods. Using the operator graph, wernshow that all partitions of the graph correspond to possible waysrnof scheduling a procedural generation on the GPU, including thernscheduling strategies of previous work. As the space of possiblernpartitions is very large, we describe three search heuristics, aidingrnan optimizer in finding the fastest valid schedule for any givenrnoperator graph. The best partitions found by our optimizer increasernperformance of 8 to 30x over the previous state of the art in GPUrnshape grammar and L-system generation.