Genetic Programming for Shader Simplification

晃晃

Genetic Programming for Shader Simplification

Abstract

We present a framework based on Genetic Programming (GP) for

automatically simplifying procedural shaders. Our approach com-

putes a series of increasingly simplified shaders that expose the in-

herent trade-off between speed and accuracy. Compared to exist-

ing automatic methods for pixel shader simplification [Olano et al.

2003; Pellacini 2005], our approach considers a wider space of code

transformations and produces faster and more faithful results. We

further demonstrate how our cost function can be rapidly evaluated

using graphics hardware, which allows tens of thousands of shader

variants to be considered during the optimization process. Our

approach is also applicable to multi-pass shaders and perceptual-

based error metrics.

Keywords: procedural texturing, pixel shaders, code simplifica-

tion, genetic programming



1 Introduction

The complexity of procedural shaders [Cook 1984; Perlin 1985] has

continued to grow alongside the steady increase in performance and

programmability of graphics hardware. Modern interactive render-

ing systems often contain hundreds of pixel shaders, each of which

may perform thousands of arithmetic operations and texture fetches

to generate a single frame.

Although this rise in complexity has brought considerable improve-

ments to the realism of interactive 3D content, there is a growing

need for automated tools to optimize procedural shaders to meet a

computational budget or set of hardware constraints. For example,

the popular virtual world Second Life allows users to supply cus-

tom models and textures, but not custom shaders: the performance

of a potentially-complex custom shader cannot be guaranteed on

all client hardware. Automatic optimization algorithms could adapt

such shaders to multiple platform capabilities while retaining the

intent of the original.

As with traditional computer programs, pixel shaders can be ex-

ecuted faster through a variety of semantics-preserving transfor-

mations like dead code elimination or constant folding [Muchnick

1997]. Unlike traditional programs, however, shaders also admit

lossy optimizations [Olano et al. 2003]. A user will likely tolerate a

shader that is incorrect in a minority of cases or that deviates from

its ideal value by a small percentage in exchange for a significant

performance boost.

One common way to achieve this type of optimization is through

code simplification. The methods proposed by Olano et al. [2003]

and Pellacini [2005] automatically generate a sequence of progres-

sively simplified versions of an input pixel shader. These may be

used in place of the original to improve performance at an accept-

able reduction in detail. However, these methods have a number

of important disadvantages. The system proposed by Olano et al.

[2003] only considers code transformations that replace a texture

with its average color. This overlooks many possible opportuni-

ties involving source-level modifications. The system proposed by

Pellacini [2005] does consider source-level simplifications. How-

ever, that approach is limited to a small number of code transfor-

mations and uses a brute-force optimization strategy that can easily

miss profitable areas of the objective function. Furthermore, both

approaches were demonstrated only on shaders that require a sin-

gle rendering pass. Modern shaders often involve multiple inter-

dependent passes. Finally, in both of these systems, only a single

error metric is used to evaluate the fidelity of a modified shader. It

would be desirable for a simplification algorithm to support a range

of error metrics, including those that are designed to predict per-

ceptual differences [Wang et al. 2004].

Intuitively, we hypothesize that a shader contains the seeds of its

own optimization: relevant functions such as sin and cos, opera-

tions such as * or +, or constants such as 1.0 are already present in

the shader source code. We propose to produce optimized shader

variants by copying, reordering and deleting the statements and ex-

pressions already available. We also hypothesize that the landscape

of possible shader variants is sufficiently complex that a simple hill-

climbing search will not suffice to avoid being trapped in local op-

tima. We thus present a novel framework for simplifying shaders

that is based on Genetic Programming (GP). GP is a computational

method inspired by biological evolution which evolves computer

programs tailored to a particular task [Koza 1992]. GP maintains

a population of program variants, each of which is evaluated for

suitability using a task-specific fitness function. High-fitness vari-

ants are selected for continued evolution. Computational analogs of

biological crossover and mutation help to locate global optima by

combining partial solutions and variations of the high-fitness pro-

grams; the process repeats until a fit program is located.

Our approach is related to recent software engineering work that

applies GP to automatic program repair [Weimer et al. 2009, 2010].

Our approach is novel not only in the domain considered (contin-

uous shader output vs. discrete software test cases) but also in the

techniques used: to take advantage of the special structure of shader

software, we apply new mutation operations, new approaches to

select a diverse population of variants, new handling for multiple

competing objectives, and optimizations to rapidly approximate the

performance of a shader variant.

Our approach offers a number of benefits over existing methods for

shader simplification. In particular, it explores optimizations be-

yond just texture lookups (cf. Olano et al. [2003]), is not limited to

an a priori set of simplifying transformations (cf. Pellacini [2005]),

does not require the user to specify continuous domains for shader

input parameters (cf. Pellacini [2005]), is demonstrably applicable

to multi-pass shaders and perceptual-based error metrics, and out-

performs previous work in a direct comparison.









全文请下载附件：

C.R.CAN

凡系斑竹滴话要听；凡系朋友滴帖要顶!

菜刀吻电线

水。。。

C.R.CAN

楼主收集的可真全哦

tc

响应天帅号召，顶

奇

你们都躲开，我来顶