A Code Motion Technique for Accelerating
General-Purpose Computation on the GPU∗
Takatoshi Ikeda, Fumihiko Ino, and Kenichi Hagihara
Graduate School of Information Science and Technology
Osaka University
1-3 Machikaneyama, Toyonaka, Osaka 560-8531, Japan{ikeda,ino,hagihara}@ist.osaka-u.ac.jp
Abstract
Recently, graphics processing units (GPUs) are providing increasingly higher performance with programmableinternal processors, namely vertex processors (VPs) andfragment processors (FPs). Such newly added capabilities motivate us to perform general-purpose computation on
GPUs (GPGPU) beyond graphics applications. Although
VPs and FPs are connected in a pipeline, many GPGPU
implementations utilize only FPs as a computational engine
in the GPU. Therefore, such implementations may result in
lower performance due to highly loaded FPs (as compared
to VPs) being a performance bottleneck in the pipeline execution. The objective of our work is to improve the performance of GPGPU programs by eliminating this bottleneck.
To achieve this, we present a code motion technique thatis capable of reducing the FP workload by moving assembly instructions appropriately from the FP program to the
VP program. We also present the deﬁnition of such movable instructions that do not change the I/O speciﬁcation
between the CPU and the GPU. The experimental results
show that (1) our technique improves the performance ofa Gaussian ﬁlter program with reducing execution time byapproximately 40% and (2) it successfully reduces the FP
workload in 10 out of 18 GPGPU programs.

1. Introduction
The GPU (graphics processing unit) [8] is a processing unit designed for accelerating compute-intensive visualization tasks, such as three-dimensional (3-D) rendering
applications [3]. Recently, GPUs are rapidly increasing∗ This work was partly supported by JSPS Grant-in-Aid for ScientiﬁcResearch for Scientiﬁc Research (B)(2)(16300006) and on Priority Areas(16016254).

1-4244-0054-6/06/$20.00 ©2006 IEEE

their performance beyond the Moore’s law [25]. For example, nVIDIA’s GeForce 6800 provides approximately 120
GFLOPS at peak performance, which equals to six 5-GHz
Pentium 4 processors [24].
In addition to this attractive performance, recent GPUs
provide ﬂexible programmabilities, such as programmableinternal processors, branch capability, and single-precision32-bit ﬂoating-point operations based on the IEEE standard[29]. These newly added programmabilities allow us to use
GPUs not only for traditional graphics applications but also
for compute-intensive, general-purpose applications.
There are many projects reporting experiences in accelerating general-purpose computation on the GPU (GPGPU)[1, 26]. From the viewpoint of implementation strategy,
these prior projects can be classiﬁed into two groups:
hardware- and software-based groups.
The former group is based on a hardware acceleration
strategy that makes use of graphics-speciﬁc components of
the GPU. For example, Lengyel et al. [20] have presented
an algorithm for robot motion planning using rasterization
hardware. Hoff et al. [15] also make use of interpolationbased polygon rasterization hardware to compute Voronoi
diagrams. Takizawa and Kobayashi [30] solve the problemof data clustering using the Z-buffer depth comparison. The
key difﬁculty in this strategy is to map CPU algorithms anddata structures onto the hardware components.
The latter group is based on the stream programming
model [18] that uses programmable components of theGPU, namely vertex processors (VPs) and fragment processors (FPs). Because current FPs provide higher arithmetic
performance than VPs, many GPGPU implementations use
only FPs as a computational engine in the GPU [26]. This
software-based strategy is more ﬂexible than the hardwarebased strategy, because it requires us to simply translate
CPU programs into GPU programs using graphics APIs.
Due to this simplicity, it is used for various scientiﬁc prob-

lems, such as physical simulation [13, 21] and numericalcomputation [5–7, 10, 12, 16, 17, 19].
Thus, many projects report successful results using theGPU. However, prior projects mainly focus on showing theperformance gain against the CPU. Accordingly, the efﬁciency of GPU implementations has not been investigatedwell. Note here that most implementations are based on
the stream programming model that uses only FPs. In thismodel, FPs may become a performance bottleneck in theGPU, because FPs and VPs are connected in a pipeline.
Therefore, it is better to ofﬂoad FPs to VPs in order tostream more data through the pipeline for higher performance.
In this paper, we present a code motion technique that
addresses the above mentioned problem for acceleration of
GPU applications. To reduce the FP workload, our technique moves assembly instructions appropriately from the
FP program to the VP program. This code motion is carriedout without changing the I/O speciﬁcation between the CPU
and the GPU, preventing us from modifying CPU programs.
Our technique is applicable to assembly programs runningon the GPU that supports Vertex Shader (VS) 1.1 [23] andPixel Shader (PS) 2.0 [23], which are standards for GPU
design.
The rest of the paper is organized as follows. We begin in Section 2 by introducing GPU architecture with its
programming strategy. We then present our code motion
technique in Section 3. Section 4 shows some experimental results and Section 5 introduces related work. Finally,
Section 6 concludes the paper.

2. GPGPU: General-Purpose Computation on
the GPUTo describe the details of our technique, we ﬁrst show abrief overview of GPGPU: the underlying architecture, assembly language, and programming strategy. In the following discussion, we assume VS 1.1 and PS 2.0 as the target
standards for our technique.

2.1. GPU Architecture
The original task of the GPU is a rendering task, which
computes pixels on the screen by projecting polygonal objects [3] (usually triangles) located in the 3-D space. In order to accelerate this compute-intensive task, the GPU isstructured in a rendering pipeline consisting of two different programmable processors: VPs and FPs.
Figure 1 shows an overview of the GPU architecture.
VPs transform 3-D triangles into 2-D triangles by projecting their vertices onto the screen from the viewing point.
In other words, this geometric transformation computes the
position of vertices on the screen, so that determines theCPU

Main memory

AGP or PCI Express bus

GPU
Vertex processors(VPs)

Video memory
3-D triangle data

2-D triangle
data
Rasterization and interpolation

Fragment
data

Texture/frame
bufferFragment processors(FPs)

Pixel data

Figure 1. GPU pipeline architecture.
screen region in which FPs operate. Then, these 2-D triangles are rasterized into fragments for input to FPs. FPs
take the responsibility for determining the ﬁnal coloring of
pixels. The details of VPs and FPs are as follows:
VP: VPs are based on a MIMD structure [11] in order torealize fast geometric transformation of vertices. Because this transformation is usually represented as a
4 × 4 transformation matrix, each processing elementof VPs has a vector processing unit that is capable of
rapid processing of 4 × 4 matrices.
The input to VPs, namely the polygonal data, mustbe transferred in advance from the main memory to
the video memory. This data transfer is performed
by a CPU program using graphics APIs such as DirectX [23] or OpenGL [28]. Then, the vertex data is
set to input registers v# in VPs (see Table 1). By using
other registers, VPs obtain transformation results, suchas the vertex coordinates and colors, and then write
them to output registers. Note here that output registers are not readable from VPs themselves.
FP: FPs are capable of rapid mapping of textures [3] (patterns) onto objects, aiming at increasing the realismof produced scenes. To do this, they obtain fragmentsfrom the rasterizer, and then execute some mathematical operations between the fragments and textures. FPs
are based on a SIMD structure [11] that allows applying the same operation simultaneously to multiple
fragments. Furthermore, as same as VPs, FPs support 4-length vector operations, because they deal with
four-component RGBA data representing red, green,
blue colors and opacity.
The fragment data is given by input registers v# and t#
in FPs (see Table 1), which indirectly receive data from

output registers oD# and oT# in VPs, respectively. The
texture data is read from the video memory using samplers s#, and the mapping results are written to buffers
on the video memory through output registers oC# andoDepth.
In summary, an execution on the GPU can be represented
as a pseudo code presented in Figure 2. The VP program is
invoked on each vertex of 3-D triangles while the FP program is invoked on each fragment inside the 2-D triangles.
The entire execution can be expressed as a doubly-nested
loop, because rasterization inside the 2-D triangles generate
fragments.
With regard to our code motion technique, the GPU architecture has three characteristics as follows.
• The input registers v# and t# in FPs hold linearly interpolated values of the output registers oD# and oT#
in VPs, respectively. That is, because the former registers hold the attributes (for example, coordinates andcolors) for a vertex, whereas the latter have those fora fragment, the input to FPs is automatically interpolated according to the relative position of fragments, as
shown in Figure 1. This interpolation is automatically
performed during rasterization. Moreover, registers v#(oD#) have lower precision than others. Each component in these registers is allowed to store 8 bits of
unsigned data in the range [0,1], whereas registers t#(oT#) can store four 32-bits of signed data.
• VPs and FPs have different capabilities, because they
do not process the same type of data: vertices and fragments. For example, FPs are capable of loading texture
data from the video memory through samplers s#, but
VPs do not have this capability. Thus, FPs have unique
instructions and registers which VPs do not have.
• There is a limitation on the number of registers thatpass data from VPs to FPs. This means that the information transmitted from a vertex to a fragment islimited by this number, because VP and FP programs
are invoked on each vertex and fragment, respectively.
In our target standards VS 1.1 and PS 2.0, there areeight t# (oT#) registers and two v# (oD#) registers.

2.2. Assembly Language for the GPU
Basically, there is no signiﬁcant difference between the
CPU assembly language and the GPU assembly language.
Instructions require a few operands as follows.
add r1, r0, c0
In this example, two vectors in source registers r0 and c0
are added and stored into the destination register r1.

Table 1. Registers in VPs and FPs. The number of registers # is speciﬁed by standards.
See [23] for details.
Unit TypeName
Read/Write
Input registerv#
R
Constant registerc#R
Temporary register
r#
R/W
VP
Address registera0
R/W
Output register
oPos, oFog, oPts
W
oD#, oT#
Input registerv#, t#
R
Constant registerc#R
FP Temporary registerr#
R/W
Samplers#
R
Output register
oC#, oDepthW
1: foreach vertex set do begin
2: Execute the VP program on VPs; // specify a region
3: Rasterize the region into fragments;
3: foreach fragment do begin
4:
Execute the FP program on FPs;
5: end6: endFigure 2. Pseudo code representing GPU execution. In this representation, our technique
can be regarded as a loop-invariant code motion technique [2], because moving instructions from FPs to VPs is equivalent to moving
them outside the inner loop.

Note here that instructions can be applied to the individual components of the vector data. To do this, we mustspecify the source/destination registers using masks: x, y, z,
and w. For example, r0.xy speciﬁes the ﬁrst and the second
components of register r0.
VP and FP programs have a limitation on program
length. This limitation is speciﬁed by the number of instruction slots required for the program. For example, VS
1.1 and PS 2.0 have a maximum constraint of 128 slots andthat of 96 slots for the VP program and the FP program,respectively. Most instructions occupy one instruction slot,
but some arithmetic instructions require more slots.
Although the number of instruction slots does not represent the precise execution time, it provides useful information to compare two instructions in terms of execution time.
Therefore, this number is useful to select the best combination of instructions, when all movable instructions cannot
be moved due to the lack of computational resources.

1: mov
2: movoPos,
oT0.xy,v0v1; vertex coordinates; texture coordinates(a); myPos = t0 (t0 is automatically set when invoked); leftPos = myPos + ﬂoat2(-1.0f/W, 0.0f); rightPos = leftPos + ﬂoat2(2.0f/W, 0.0f)
1: movr0.z,
t0.y
2: movr1.y,
c4.x; 0.0f
3: movr0.y,
c4.x
4: rcpr0.w,
c3.x; -1.0f/W
5: movr0.x,-r0.w
6: addr1.x,
r0.w, r0.w ; 2.0f/W
7: addr0.xy, r0,
t0
8: add
r1.x,
r1.x,
r0.x
9: add
r1.y,
r0.z,
r1.y
; set xn−1 , xn+1 , and xn as texture data at; leftPos, rightPos, and myPos, respectively
10: texld r2,
r0,
s0
11: texld r0,
r1,
s0
12: texld r1,
t0,
1 s0
; convolution: yn = k=−1 ck xn+k
13: mul
r2,
r2,
c0.x
14: mad
r1,
c1.x,
r1,
r2
15: mad
r0,
c2.x,
r0,
r1
16: mov
oC0,r0; output yn

Table 2. Instructions available only on FPs.
Capability
Instruction
Texture reference
texkil, texld, texldb, texldp
Conditional selection cmp, cnd
Dot product and add
dp2addFigure 3 shows an example of VP and FP programs
developed according to the stream programming model.
These programs implement a 1-D convolution ﬁlter thatsmoothes a 2-D image. In this example, four vertices of arectangle are given to VPs, and then VPs simply output two
coordinates for each vertex: the coordinates on the screen(oPos) and those on the texture (oT0.xy). FPs receive aninterpolated value (t0), namely the texture coordinates for a
fragment. The FP program implements the convolution operation on each fragment, accessing its left and right neighbors. Because the texture coordinates are speciﬁed in therange [0,1], the relative coordinates of the left neighbor are
given by (-1.0f/W, 0.0f), where W is the texture width.
In summary, many GPGPU implementations use thestream programming model due to its simplicity. However,VPs are not used well in this model, motivating us to move
instructions from highly-loaded FPs to VPs.

3. Code Motion Technique(b)

Figure 3. Example of (a) VP and (b) FP programs performing 1-D convolution. W represents the texture width. See text for detail.

2.3. Programming Strategy for GPGPU
In modern GPUs, FPs provide higher performance thanVPs, because rendering tasks usually need to process more
fragments than vertices, as presented in Figure 2. Therefore, most GPGPU implementations use FPs as a computational engine in the GPU [26]. They regard FPs as a stream
processor [18] and use VPs only for informing FPs of theworking region. Thus, data is passed through VPs.
This strategy is called the stream programming model[18], which exploits the data parallelism inherent in the application by organizing data into streams and expressing
computation as kernels that operate on streams. Streams
here are usually stored as texture data, which can be fetched
to FPs by samplers. A kernel is implemented as a FP program. The computed results can be transferred (readback)from the video memory to the main memory by using thegraphics APIs mentioned in Section 2.1.

We now present our technique that aims at accelerating
GPU programs by moving instructions from FPs to VPs.
The problem here is that, given a pair of VP and FP programs, (1) which instructions are movable and (2) how these
programs can be modiﬁed without changing the computational results.

3.1. Deﬁnition of Movable Instructions
To apply our technique to GPU programs, we have to
make clear which instructions are allowed to move from FPs
to VPs. This section presents the deﬁnition for such movable instructions. To deﬁne this, we basically focus on thethree characteristics mentioned in the end of Section 2.1. In
the following, we explain the deﬁnition using the example
in Figure 3.
We deﬁne movable instructions such that they satisfy allof the following four conditions C1–C4:
C1. Executability: Movable instructions must be executable on VPs as well as on FPs. However, the instruction set available on VPs is not exactly the sameas that available on FPs, as shown in Table 2. For example, the texld instruction cannot be moved to VPs,
because VPs do not have a read capability to textures.

Therefore, in Figure 3(b), the texld instructions in lines
10–12 must be stay ﬁxed in the FP program.
C2. Accessibility: As same as the limitations on instructions, some FP registers also have unique capabilities
that VP registers do not have. Such unique registers
are samplers s# and output registers oC# and oDepth.
Samplers cannot be replaced by any register in VPs,
because they are unique in terms of sampling a texture.
Similarly, output registers are also unique in terms of
having a write capability to the video memory. Thus,
instructions accessing these unique registers cannot be
moved to VPs. Note here that constant values are movable to VPs, because they are set by the VP/FP program, and thus are ﬁxed before program execution. In
Figure 3(b), the instructions in lines 10–12 and 16 must
be in the FP program, because they access sampler s0
or output register oC0.
C3. Equivalency: Only linear operations can be moved to
VPs, because FPs receive linearly interpolated datafrom VPs. Otherwise, namely if we move non-linear
operations to VPs, we have wrong results due to the automated interpolation. Formally, this condition can be
expressed as follows: computation C on FPs is movable if C(L(V)) = L(C(V)), where L is the linear
interpolation and V is the original output of VPs. In
addition to this linearity of computation, we have toconsider the precision of registers. That is, lower precision registers v# (oD#) cannot be used to pass highprecision data from VPs to FPs. Otherwise, we obtainwrong results due to round-off errors.
C4. Dependability: In addition to the GPU-oriented limitations mentioned above, we also have to consider data
dependencies between instructions, because our code
motion technique changes the execution order of instructions. Actually, Figure 2 indicates that moving
an instruction to the VP program means that the instruction will be executed prior to all instructions in
the FP program. Therefore, we must avoid the collapseof data dependencies in order to obtain correct results.
Thus, an instruction is movable if all instructions thathave a dependency on the instruction are also movable.
In Figure 3(b), the instructions in lines 13–16 are not
movable due to the dependencies from the unmovable
texld instructions in lines 10–12.
According to the conditions mentioned above, our technique determines that the instructions in lines 1–9 are movable to VPs. These instructions intend to compute the coordinates in a texture in order to fetch the left and right neighbors. This address computation can be precomputed by
VPs, because it satisﬁes condition C3 in addition to C1, C2,

VP

v0

v1

1

2

VP
v0
1

oPos oT0.xy

v1
2

c4.x

3

4

c3.x
5

Interpolation

FP t0

c4.x

6
7

8

c3.x
9

1

2

3

13

4
5

oPos oT0.xy

6

oT1.xyoT2.xInterpolation

7
9

oT2.y

11

8

FP

r1.y
r0.xy
r1.x
used by the texld instruction

(a)

t1

t2

1

2

(b)

Figure 4. A portion of a directed acyclic graphrepresenting data dependencies (a) beforeand (b) after code motion. A node ID represents the line number in the program. Underlined registers are modiﬁed to obtain correct
results.

and C4. That is, the coordinates of the left and right neighbors (leftPos and rightPos) do not change whether they arecomputed for each fragment (after interpolation) or for eachvertex (before interpolation).

3.2. Code Motion Strategy
The next question is how instructions should be moved to
the VP program in a proper manner. Our technique moves
the code in the following three steps (see Figures 4 and 5).
1. Code movement: We add the code at the end of the
VP program, as shown in Figure 5(a). At that point,since VPs have completed the original computation,
the concatenated code is allowed to use all temporary
registers in VPs.
2. Modiﬁcation on inputs: The inputs to the code must
be changed to obtain them directly in the VP program.
Such inputs are values (1) in the FP input registers t#
and (2) in constant registers c# (see Figure 4(a)). For
the former case, we add some instructions in the VP
program in order to save the origin of the VP output
registers oT# as the new inputs to the code. However, these additional instructions are not required formost GPGPU implementations, which do not change
the values of input registers v#. Thus, in most cases,
we are allowed to replace operands t# with v# (lines 3
and 9 in Figure 5(a)). For the latter case, we replace
operands c# with other unused c# if necessary.

→
→
→
→
→
→
→
+
→
+
→
+

1: mov
2: mov
3: mov
4: mov
5: mov
6: rcp7: mov
8: add9: add
10: mov
11: add
12: mov
13: add
14: mov

oPos,
oT0.xy,
r0.z,
r1.y,
r0.y,
r0.w,
r0.x,
r1.x,
r0.xy,
oT1.xy,r1.x,
oT2.x,
r1.y,
oT2.y,

v0
v1
v1.y
c4.x
c4.x
c3.x
-r0.w
r0.w,
r0,
r0.xy
r1.x,
r1.x
r0.z,
r1.y

; 0.0f; -1.0f/W
r0.w
v1; 2.0f/W

r0.x
r1.y

(a)

1: texld
2: texld
3: texld
4: mul5: mad6: mad7: mov

r2,
r0,
r1,
r2,
r1,
r0,
oC0,

t1,
t2,
t0,
r2,
c1.x,
c2.x,
r0

Table 3. Experimental environments.
Component
Speciﬁcation
CPU
Pentium 4 3.0-GHz
Main memory
1 GB
Graphics bus
AGP 8XGPUATI Radeon X800 Pro
Core clock 475 MHz
Video memory 256 MB
6 VPs and 12 FPs
Operating system Windows 2000
Graphics API
DirectX 9.0 [23]

s0
s0
s0
c0.x
r1,
r0,

r2
r1

(b)

Figure 5. Example of (a) VP and (b) FP programs after code motion. See Figure 3 for theoriginal program. Instructions marked withnotations ‘→’ and ‘+’ are those moved fromthe FP program and those added during code
motion, respectively. Underlined operands
are changed to obtain correct results.

3. Modiﬁcation on outputs: The data obtained by the
new code must be sent properly to FPs. To do this,we add an instruction that sets the data to the unused
output registers oT# in VPs (lines 10, 12, and 14 in
Figure 5(a)). The data must also be received by FPs.
Therefore, we replace the operands that refer the datawith the unused input registers t# in FPs (lines 1 and
2 in Figure 5(b)). Note here that a proper pair of input/output registers must be selected to avoid passing
data to wrong registers.

the number of instruction slots in FPs from 16 to 7 slots,
but increases that in VPs from 2 to 14 slots. Therefore, wemust give priorities to movable instructions if these computational resources are not sufﬁcient to move all of them.
In such a case, we currently select a combination of instructions that minimizes the number of instructions slots
required for the FP program.
Our technique reduces the number of instructions per
fragment, and thereby reduces execution time spent for the
FP program. In contrast to this timing beneﬁt, there aresome disadvantages in our technique. One apparent disadvantage is that it takes more time on VPs due to increased
instructions in the VP program. The other disadvantage isthat, more data is passed from VPs to FPs, so that this increase may decrease the entire performance if the rasterizer
would become a performance bottleneck.
Despite the disadvantages mentioned above, we thinkthat our technique is effective in improving the performanceof typical GPGPU programs. As we mentioned in Section
2.3, such programs usually use FPs as a computational engine and access textures to fetch data. In this programming
model, there are many instructions for computing the texture coordinates, which are usually movable instructions, aspresented later in Section 4.

4. Experimental Results
We now present some experimental results showing theeffectiveness of our technique. We investigate the techniquefrom the following two viewpoints: the reduction of execution time and the improvability for a variety of GPU programs. Table 3 shows the speciﬁcation of the experimental
machine, which consists of commodity hardware.

3.3. Code Selection Strategy
4.1. Timing Results
Although our code motion technique reduces the instruction slots used in FPs, it requires (1) more instruction slots
in VPs and (2) more registers for passing data from VPs
to FPs. For example, in Figure 5, our technique reduces

We apply our technique to a Gaussian ﬁlter thatsmoothes an N × N pixel image. Pixels here are stored
in a 32-bit RGBA format. The kernel size of the ﬁlter is set

Table 4. Timing results for a Gaussian ﬁlter with kernel size of K × K pixel, where K = 13. V andF represents the number of instruction slots required for VP and FP programs, respectively. Ratio
represents the reduction percentage of FP slot or time.
V(slot)

Instructions
F
Ratio(slot) RF (%)

2

63

—

6

60

5

9

57

10

12

54

14

15

51

19

18

48

24

21

45

29

23

43

32

Image
size
N
256
512
768
1024
256
512
768
1024
256
512
768
1024
256
512
768
1024
256
512
768
1024
256
512
768
1024
256
512
768
1024
256
512
768
1024

Filtering
Time
Ratio
t (ms) Rt (%)
1.3
—
4.9
—
10.9
—
19.5
—
1.2
6
4.7
6
10.3
6
18.2
7
1.2
11
4.4
11
9.7
11
17.2
11
1.1
17
4.1
17
9.1
17
16.1
18
1.0
22
3.8
23
8.4
23
14.9
23
0.9
28
3.5
29
7.8
29
13.8
29
0.9
33
3.2
34
7.2
34
12.7
35
0.8
39
3.0
40
6.6
40
11.6
40

to be K × K pixel. This 2-D ﬁlter is realized using 1-D
ﬁltering in the horizontal and vertical directions. The initial implementation is typically developed according to thestream programming model. It requires 2 slots for the VP
program and 63 slots for the FP program.
There are 20 movable instructions composing 7 independent groups in terms of data dependencies. Accordingly,
if all groups are moved, the VP program requires approximately 20 instruction slots and 7 oT# (t#) registers in addition to the initial usage. Because we have enough registers
and instruction slots to move all groups, we then move themin a stepwise manner to investigate the relationship between
the reduction of instruction slots and that of execution time.
Table 4 shows the results. In the following discussion, let V

Readback
Time
(ms)
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0
2.0
5.3
11.9
21.0

Total
Time
Ratio
T (ms) RT (%)
3.3
—
10.2
—
22.8
—
40.5
—
3.2
2
10.0
3
22.2
3
39.2
3
3.2
4
9.7
5
21.6
6
38.2
5
3.1
6
9.4
8
21.0
8
37.1
8
3.0
9
9.1
11
20.3
11
35.9
11
2.9
11
8.8
14
19.7
14
34.8
14
2.9
13
8.5
16
19.1
17
33.7
17
2.8
15
8.3
19
18.5
19
32.6
19

Performance
12KN 2 /t(GFLOPS)
7.8
8.3
8.4
8.4
8.3
8.8
8.9
9.0
8.8
9.4
9.5
9.5
9.4
10.0
10.1
10.2
10.0
10.7
10.9
11.0
10.8
11.6
11.8
11.8
11.7
12.6
12.8
12.9
12.8
13.8
14.0
14.1

and F be the number of instruction slots consumed by the
VP program and the FP program, respectively.
As we move more groups to the VP program, the FP
program uses less instruction slots F , ﬁnally achieving aminimum of 43 slots. On the other hand, the VP program
requires more slots V , resulting in a maximum of 23 slots.
Thus, we generate seven variations in addition to the initial
implementation.
We then measure the execution time of these eight implementations with varying the size of image N from 256
to 1024 pixels. In Table 4, Notation T represents the total
time of implementation, containing (1) the ﬁltering time tspent on the GPU and (2) the readback time required fordata transfer from video memory to main memory. Note

here that time t includes the initialization time for sending
data from main memory to video memory. This initial procedure is automatically processed by underlying APIs, andthus we cannot separate the initialization time from the processing time. Ratio RF , Rt , and RT represent the reduction
percentage as compared to the original implementation.
For all implementations, we obtain ratio Rt > 0, sothat our technique successfully reduces the ﬁltering timet. When we move all movable instructions (F = 43),
we obtain the best result with achieving 39–40% reductions
against the original implementation. These reductions canbe explained by comparing ratio Rt with RF . These ratios
show a linear relationship between the reduction of execution time and that of instruction slots. That is, the numberof instruction slots F affects the execution time t on theGPU. Therefore, F can be used as a selection measure forminimizing time t if all instructions cannot be moved.
The disadvantages mentioned in Section 3.3 are not revealed in the timing results, because the FP program is executed much more time as compared to the VP program. In
our implementation, given an N × N pixel image, the VP
program is invoked only four times to process the verticesof the image while the FP program is invoked N 2 times toprocess all fragments. Actually, on the experimental machine with 6 VPs and 12 FPs, the FP program is executedat least 213 times as much as the VP program. Therefore,in typical GPGPU implementations, we will achieve higher
performance as we move more instructions, even though the
VP program takes more time.
Although our technique achieves 39–40% reductions,these percentages are not the same as those observed in the
total time T (15–19%). These less reductions are due tothe readback time, which takes relatively long time as compared with the ﬁltering time. Thus, the readback of textures
is not so fast on our machine whose GPU is connected by an
AGP bus. Because the AGP bus provides a low bandwidthof 266 MB/s from video memory to main memory (2.1 GB/s
for the opposite direction), this problem will be resolved byusing faster interconnects such as PCI Express buses, which
provide a bandwidth of 4 GB/s for both directions.

4.2. Improvability
We next apply our technique to a variety of GPU programs: (1) 4 kernels each implementing 1-D and 2-D convolution, integer sorting, and summation; (2) 13 kernels
composing a Navier-Stokes ﬂuid simulator [27]. Because
it originally does not have a VP program, we have added a
VP program that simply pass data to FPs, as presented in
Figure 3(a); and (3) 9 shader programs [9] as examples ofgraphics (non-GPGPU) applications. These shaders apply avisual effect to rendering objects.
As shown in Tables 5 and 6, our technique successfully

Table 5. Number of instructions before andafter applying our technique. Ratio represents the reduction percentage of FP slots.
Kernel
1-D convolution
2-D convolution
Sorting
Summation

Before
V
F
2 63
2 55
2 40
2 16

After
V
F
23 44
40 47
14 40
9
9

Ratio
RF (%)
30
15
044Table 6. Number of instructions in a ﬂuid simulator [27].
KernelActuallyRender
Clear
Copy
Add
Splat
ScrollScroll2
VortexDivergence
Subgradient
Jacobi
AdvectDisplay

Before
V
F
2
1
2
2
2
2
2
6
2
9
2 11
2 11
2 16
2 17
2 19
2 21
2 34
2 41

After
V
F
2
1
2
2
2
2
2
6
2
9
8
5
8
5
2 16
10
9
10 11
10 13
2 34
10 33

Ratio (%)
RF Rt
0
—
0
—
0
—
0
—
0
—
55
15
55
11
0
—
47
37
42
39
38
37
0
—
20
20

reduces the number of instruction slots F in 9 out of 17
kernels. Among these kernels, Scroll and Scroll2 kernels
achieve the best reduction of 55% in terms of slots F . Thesekernels are similar to the example in Figure 3, because theymainly consists of address computation for two texture references. Thus, address computation is one of the typicalcomputations that can ofﬂoad FPs to VPs. Note here that the
55% reduction results in about 15% less time in these cases.
This small effect is due to the initialization time mentioned
in Section 4.1, because this overhead is relatively large inthese small kernels.
On the other hand, Advect kernel results in no improvement, though it consumes relatively many instruction slots
F , as compared to the others. The reason for this is that, it
performs many texture references, which are not executable
on VPs, and moreover, all instructions have data dependencies from these texture data. Also, Sorting kernel in Table
5 fails to reduce instruction slots F . However, this kernel
is improved by exchanging the execution order of instructions, which is automatically generated by a compiler. Thiscan be explained as follows. Suppose that we have two instructions, r = a then r+= b, and operands a and b are un-Table 7. Number of instructions in shaderprograms [9].
Shader program
Multitexture shader
Dot-3 bump mapping
Toon shader
Ambient shading
Diffuse shader
Lambertial diffuse shader
Shilhouette shader
Fresnel shaderPhon-blinn

Before
V
F
8
3
19
3
28
9
6 —
9 —
12 —
20 —
20 —
25 —

After
V
F
8
3
19
3
28
9
6 —
9 —
12 —
20 —
20 —
25 —

Ratio
RF (%)
0
0
0
—
—
—
—
—
—

movable and movable, respectively. In this case, we cannot
move both instructions, but if we exchange them, r=b thenr+=a, we can move the ﬁrst instruction to VPs.
In contrast to the GPGPU programs mentioned above,
all shader programs fail to reduce instruction slots F (Table
7). These shaders do not utilize the programmability of FPs,
and thus do not have FP programs.
In summary, address computation for texture references
is typically movable instructions. Reordering instructions
could yield further improvement. On the other hand, there
will be no improvement if the FP program has (1) few instruction and (2) many data dependencies from texture data,
especially if such dependencies exist in the beginning of the
FP program.

5. Related WorkTo the best of our knowledge, there are a few papers[7,12,16,17] that try to improve the performance of GPGPU
applications. Hall et al. [12] present cache-aware algorithms for matrix multiplication on the GPU. Their algorithms are evaluated by Fatahalian et al. [7] using realGPUs. These cache-aware algorithms are speciﬁc to matrix multiplication. On the other hand, our technique does
not depend on particular applications. Also our technique
is a post-compile optimization approach, so that it does notneed any modiﬁcation to underlying algorithms.
Jiang et al. [17] also try to improve the performance of
matrix multiplication. They automate the tuning process byselecting the best implementation from multiple versions
according to empirical evaluation. Their tuning strategy
is similar to that in ATLAS [31] in terms of employing
parameterized code generators that can generate multiple
codes according to input tuning parameter values. A similar
study [16] is also presented for LU decomposition. Because
these projects optimize only the FP program, our optimization approach is unique in that it ofﬂoads FPs to VPs.

Because our technique optimizes assembly programs, it
can be integrated with high-level compilers. For example,
it can work as a post-compile optimization technique by using assembly code generated by high-level compilers suchas Brook [6] and Cg [22]. Note here that Brook is designed
for GPGPU applications but it employs only FPs as a computational engine. Cg generates efﬁcient code but the optimization is independently applied to each of the VP and FP
programs.
With respect to graphics applications, many techniques
have been proposed to improve the rendering performance[8]. These techniques ﬁrst ﬁnd a performance bottleneck in
the pipeline execution, and then try to reduce the amountof data streams that go through the bottleneck. For example, they simplify or eliminate polygonal objects to reduce
the number of vertices if VPs limit the entire performance.
These reduction-based techniques are effective to graphics
applications, which are allowed to reduce the level of details in the output scene. However, they cannot be applied
to GPGPU applications, which must not omit computations
that change the computational results.
As we presented in Figure 2, moving instructions from
FPs to VPs corresponds to moving them outside the inner
fragment loop. Therefore, in this interpretation, our code
motion technique can be regarded as a loop-invariant code
motion technique [2, 4], which aims at reducing the computational amount of the entire loop. This computational
reduction is also effective for future GPUs that will integrate VPs and FPs into uniﬁed sharders. Such GPUs will becapable of dynamically allocating uniﬁed sharders to vertex
or fragment operations, so computational reduction plays animportant role in achieving the best resource allocation.

6. Conclusions
We have presented a code motion technique that aims
at accelerating GPU applications by moving assembly instructions from FPs to VPs. Our technique differs fromprior techniques in terms of the following points: our approach ofﬂoads FPs to VPs, so that differs from other approaches that independently optimizes each of the VP and
FP programs; our post-compile optimization can be integrated with high-level compilers; and our technique keeps
the same I/O speciﬁcation between the CPU and the GPU,
allowing us to use CPU programs without any modiﬁcation.
The experimental results show that (1) our technique reduces execution time of a Gaussian ﬁlter by approximately
40%; (2) it successfully reduces the FP workload in 10 out
of 18 GPGPU programs; and (3) there is a linear relationship between the reduction of FP instruction slots and thatof the ﬁltering time. Thus, The effectiveness of the technique depends on the number of instructions moved to VPs.
In current GPUs, this is usually limited by the number ofregisters that pass data from VPs to FPs.
One future work is to verify the computational results interms of error. As we mentioned before, FPs and VPs havedifferent designs. Therefore, by moving instructions from
FPs to VPs, the results might be changed due to this difference. Although we have conﬁrmed that the experimental
programs return the same results, we think more detailed
veriﬁcations are needed, because the GPU seems not be rigorous with errors [14]. We are also planning on developing
a tool to automate the code motion procedure.

References[1] General-Purpose Computation Using Graphics Hardware,
2005. http://www.gpgpu.org/.
[2] A. V. Aho, R. Sethi, and J. D. Ullman, editors. Compilers:
Principles, Techniques, and Tools. Addison-Wesley, Reading, MA, 1986.
[3] T. Akenine-Möller and E. Haines, editors. Real-Time Rendering. Morgan Kaufmann, San Mateo, CA, second edition,
July 2002.
[4] D. F. Bacon, S. L. Graham, and O. J. Sharp. Compiler transformations for high-performance computing. ACM Computing Surveys, 26(4):345–420, Dec. 1994.
[5] J. Bolz, I. Farmer, E. Grinspun, and P. Schröder. Sparse matrix solvers on the GPU: Conjugate gradients and multigrid.
ACM Trans. Graphics, 22(3):917–924, July 2003.
[6] I. Buck, T. Foley, D. Horn, J. Sugerman, K. Fatahalian,
M. Houston, and P. Hanrahan. Brook for GPUs: Stream
computing on graphics hardware. ACM Trans. Graphics,
23(3):777–786, Aug. 2004.
[7] K. Fatahalian, J. Sugerman, and P. Hanrahan. Understanding
the efﬁciency of GPU algorithms for matrix-matrix multiplication. In Proc. SIGGRAPH/EUROGRAPHICS Workshop
Graphics Hardware (GH’04), pages 133–137, Aug. 2004.
[8] R. Fernando, M. Harris, M. Wloka, and C. Zeller. Programming graphics hardware. In EUROGRAPHICS 2004 Tutorial Note, Aug. 2004.
[9] R. Fosner. Real-Time Shader Programming. Morgan Kaufmann, San Mateo, CA, 2003.
[10] N. Galoppo, N. K. Govindaraju, M. Henson, and
D. Manocha. LU-GPU: Efﬁcient algorithms for solving
dense linear systems on graphics hardware. In Proc. Int’l
Conf. High Performance Computing, Networking, Storage
and Analysis (SC2005), Nov. 2005.
[11] A. Grama, A. Gupta, G. Karypis, and V. Kumar. Introduction to Parallel Computing. Addison-Wesley, Reading, MA,
second edition, Jan. 2003.
[12] J. D. Hall, N. A. Carr, and J. C. Hart. Cache and bandwidthaware matrix multiplication on the GPU. Technical Report
UIUCDCS-R-2003-2328, University of Illinois, Mar. 2003.
[13] M. J. Harris, G. Coombe, T. Scheuermann, and A. Lastra.
Physically-based visual simulation on graphics hardware.
In Proc. SIGGRAPH/EUROGRAPHICS Workshop Graphics Hardware (GH’02), pages 109–118, Sept. 2002.
[14] K. E. Hillesland and A. Lastra. GPU ﬂoating point paranoia.
In Proc. 1st ACM Workshop General-Purpose Computing on
Graphics Processors (GP2 ’04), pages C–8, Aug. 2004.

[15] K. E. Hoff, T. Culver, J. Keyser, M. Lin, and D. Manocha.
Fast computation of generalized Voronoi diagrams using
computer graphics hardware. In Proc. SIGGRAPH’99,
pages 277–286, Aug. 1999.
[16] F. Ino, M. Matsui, and K. Hagihara. Performance study of
LU decomposition on the programmable GPU. In Proc. 12thInt’l Conf. High Performance Computing (HiPC’05), pages
83–94, Dec. 2005.
[17] C. Jiang and M. Snir. Automatic tuning matrix multiplication performance on graphics hardware. In Proc. 14th Int’l
Conf. Parallel Architectures and Compilation Techniques(PACT’05), pages 185–196, Sept. 2005.
[18] B. Khailany, W. J. Dally, U. J. Kapasi, P. Mattson,
J. Namkoong, J. D. Owens, B. Towles, A. Chang, andS. Rixner. Imagine: Media processing with streams. IEEE
Micro, 21(2):35–46, Mar. 2001.
[19] E. S. Larsen and D. McAllister. Fast matrix multiplies usinggraphics hardware. In Proc. Int’l Conf. High Performance
Computing and Communications (SC2001), Nov. 2001.
[20] J. Lengyel, M. Reichert, B. R. Donald, and D. P.Greenberg.
Real-time robot motion planning using rasterizing computer
graphics hardware. In Proc. SIGGRAPH’90, pages 327–
335, Aug. 1990.
[21] W. Li, X. Wei, and A. Kaufman. Implementing lattice Boltzmann computation on graphics hardware. The Visual Computer, 19(7/8):444–456, Dec. 2003.
[22] W. R. Mark, R. S. Glanville, K. Akeley, and M. J. Kilgard.
Cg: A system for programming graphics hardware in a Clike language. ACM Trans. Graphics, 22(3):896–897, July
2003.
[23] Microsoft
Corporation.
DirectX,Asm
Shader
Reference,2005.
http://msdn.microsoft.com/library/default.asp?url=/library/en-us/directx9 c/directx/graphics/reference/reference.asp.
[24] J. Montrym and H. Moreton. The GeForce 6800. IEEE
Micro, 25(2):41–51, Mar. 2005.
[25] G. E. Moore. Cramming more components onto integrated
circuits. Electronics, 38(8):114–117, Apr. 1965.
[26] J. D. Owens, D. Luebke, N. Govindaraju, M. Harris,
J. Krüger, A. E. Lefohn, and T. J. Purcell. A survey ofgeneral-purpose computation on graphics hardware. In EUROGRAPHICS 2005, State of the Art Report, pages 21–51,
Aug. 2005.
[27] V. Palmer. Navier-Stokes ﬂuid simulator, Dec. 2004.
http://www.strangebunny.com/techdemo stokes.php.
[28] D. Shreiner, M. Woo, J. Neider, and T. Davis. OpenGL Programming Guide. Addison-Wesley, Reading, MA, fourth
edition, Dec. 2003.
[29] D. Stevenson. A proposed standard for binary ﬂoating-point
arithmetic. IEEE Computer, 14(3):51–62, Mar. 1981.
[30] H. Takizawa and H. Kobayashi. Multi-grain parallel processing of data-clustering on programmable graphics hardware. In Proc. 2nd Int’l Symp. Parallel and Distributed
Processing and Applications (ISPA’04), pages 16–27, Dec.
2004.
[31] R. C. Whaley, A. Petitet, and J. J. Dongarra. Automatedempirical optimizations of software and the ATLAS project.
Parallel Computing, 27(1/2):3–35, Jan. 2001.