Frame Buffer Compression Using a Limited-Size Code Book for Low-Power
Display Systems
Hojun Shim,Youngjin Cho and Naehyuck Chang
School of Computer Science&Engineering,Seoul National University,Korea
naehyuck@snu.ac.kr
Abstract
Modern hand-held multimedia terminals consume signifi-cant power for their quality display devices.Due to60Hz or higher LCD refresh operations,frame buffer memory and related bus become dominant power consumers.In this paper,we introduce an efficient frame buffer compression scheme that us differential Huffman coding and its hard-ware implementation.The compression and decompression must be simple and not incur distinct power overhead in-volving no CPU operations.We have achieved both on-the-fly compression and high compression efficiency devising a limited-size code book,color-difference reduction tech-niques and an adaptive code book update scheme.On the MobileMark2002benchmark,our techniques reduce the frame buffer activity by52%to
90%,saving up to86mW including the overhead.
1.Introduction
Even miniature portable multimedia terminals now de-mand high-resolution,high-color LCDs(Liquid Crystal Displays).Thus,high-wattage backlight lamps and large-capacity frame buffer memories,which together lead to high power consumption.
High-level power reduction techniques generally utilize slack time to reduce the power consumption;but there is no explicit slack time in display systems,regardless of the computational burden,as long as the display panel is turned on.Recent works[3,4]have introduced power reduction techniques for LCD display.Backlight lamps are the most power-hungry components in display systems,and many techniques for reducing backlight power have been pro-pod[2,5].
Together with the backlight,frame buffers consume sig-nificant power.LCD controllers should periodically refresh the display at60Hz,or an even higher sweep rate,and frame buffers shows therefore high activities.Thus,reduc-ing frame buffer activity helps longer battery life.In our previous work[7]we have introduced frame buffer com-pression to reduce its power consumption since the frame buffer occupies over20%of the total power of the system. Our previous work us single-pass
adaptive run-length en-coding(RLE)compression and adds an incremental re-compression scheme to permit frequent partial frame buffer updates.Although adaptive RLE compression is simple and efficient,its compression performance is not only very poor at supporting progressive changes of colors,but also highly vulnerable to the distribution of color over the screen.It also requires an additional bit which reduces the effective color-depth of the original image.
In this paper,we introduce a new frame buffer compres-sion technique,bad on differential Huffman coding.It exhibits better and more robust compression than the pre-vious adaptive RLE compression algorithm,becau it uti-lizes spatial correlations in the frame buffer contents more effectively.It also us a limited-size code book with pro-pod color-difference reduction techniques to minimize the power and area overhead in its hardware implementation. We also prent an adaptive code book update scheme that exploits temporal correlations in the frame buffer contents for a particular application when a ur runs veral appli-cations simultaneously.
2.Frame buffer compression using a code book 2.1Image compression
Huffman coding[6]is the best-known lossless variable length encoding(VLE)technique,but the symbol frequen-cies must be known before code generation.Arithmetic coding[6]guarantees lossless optimal
encoding,but it still requires expensive iterative encoding and decoding proce-dures.Another approach is Lempel-Ziv-Welch(LZW)[6] compression,which is a single-passfixed-length lossless encoding technique which replaces a string of symbol with a single code word using a sliding dictionary.
However,none of the techniques are suitable for very large numbers of symbols,such as color values reprented by relatively long integers.They are optimized for small numbers of symbols,such as ASCII codes.Graphic appli-cations are only possible when the color depth 元旦什么时候
is quite low. For example,LZW compression is ud in the GIF(graph-ics interchange format)[6]standard,which allows only256 colors.
2.2Frame buffer compression
Our approach to frame buffer compression aims at reducing the number of frame buffer access and thus the power con-sumption without compromising the image quality.Fig.1 illustrates the basic structure of o天麻的功效和作用
ur frame buffer compres-sion.We assume a parate frame buffer memory with a structure that is almost standard except for some low-cost products.It has both compresd and decompresd pages. Compresd pages are managed by the LCD controller, which compress th
e contents of decompresd pages dur-ing sweep operations.Once an LCD controller has com-presd the contents of the frame buffer,it can access the compresd data instead of the original decompresd data to refresh the screen.That can reduce the frame buffer access activity by a factor approaching the compression rate.Additional frame buffer access for compression are only far less frequent write-back operations to compresd pages.
Figure1.Frame buffer compression((a)images drawn by the CPU,(b)displaying a decompresd image, (c)on-the-fly compression,and(d)displaying a com-presd image).
The energy consumption of the frame buffer and its as-sociated bus is proportional to the number of frame buffer access during sweep operations.The number of access is in turn determined by
the screen resolution,the sweep (refresh)rate and the color depth.In this paper,we assume the following display system configuration:VGA(640480)screen resolution,60-Hz refresh rate and16-bpp(bits per pixel)color depth.The number of frame buffer access during a refresh period,N f b,is given by
N f b=V S H S
L f b
,(1)
where V S and H S are the vertical and horizontal screen reso-lution,and L f b is the burst length of a frame buffer access in pixels.Frame buffer compression aims at reducing the num-ber of frame buffer access(N f b)and thus saves power.
2.3Distributions of colors and color differences The apparent visual entropy of the screen image decreas significantly when we look at color differences instead of color values,due to spatial correlations in the frame buffer contents.The color difference of the pixel C i,j at screen coordinate(i,j),where2≤i≤H S and1≤j≤V S,is defined as
C i,j=C i,j−C i−1,j.(2) The color data occupying most of the screen can be rep-rented by a small number of color differences,for the MobileMark2002benchmark applications,which are ex-plained in Section4.2.Table1summarizes the number of colors and color differences ud to display the applica-tion window in each application.Among the applications, Photoshop is the worst ca for compression in terms of the number of colors and color differences ud in 购物消费的感受
a single ap-plication.
We define the critical colors as the t of colors that is required to reprent over90%of the area of the screen. Similarly,we define the critical color differences as the t of color differences that is required to reprent over90%of the area of the screen.The number of critical color differ-ences does not exceed32,except for the Photoshop appli-cation.When the Photoshop and Flash applications are dis-playing a large high-color(16-bpp)photo image,they u much fewer critical color differences than critical colors.
Table1.The number of colors and color differences.
Critical Color Critical
Colors
lor diffs.
Photoshop6367980270569
Flash3066212162425
Word14131992
Excel10451833 PowerPoint140335212718
Slide show3242419437
Outlook10962577 Communicator5954213873
Table2.Compression rates(R)achieved by adaptive RLE,differential Huffman coding and differential Huff-man coding with a limited-size code book(%).
Diff.Huffman
Adaptive
Diff.
coding with
RLE
Huffman
a limited-size
coding
code book Photoshop71.0232.0647.17
Flash39.6619.0138.50
Word14.958.889.64
Excel28.6910.9611.63 PowerPoint44.9619.4027.86
Slide show69.5521.2226.94
Outlook26.3612.6514.90 Communicator24.2311.8019.27
2.4Differential Huffman coding
We perform Huffman coding on color differences in the frame buffer.Differential Huffman coding is superior to adaptive RLE in terms of the compression rate(e Table2). But differential Huffman coding is not a single-pass com-pression technique,since it needs to profile the frequency of every possible color difference in advance.It is really difficult to run a Huffman coding algorithm fast enough for frame buffer compression due to the time-consuming code construction process.The worst-ca execution time of this process is bounded by O(N log2N)for N symbols and thus by O(n2n)for the n-bpp color depth of the frame buffer. Additionally,the area overhead of the compression logic increas exponentially as the frame buffer color depth in-creas becau of the need to manage2n symbols.
2.5Differential Huffman coding with a limited-
size code book
Differential Huffman coding with a limited-size code book aims at more effective compression of the frame buffer con-tents,considering both the time complexity and the area overhead.We u a limited number(X)of critical color dif-ferences to reduce the number of symbols for Huffman cod-ing simply becau we cannot manage2n symbols.Fig.2 shows the structure of an X-entry limited-size code bo
ok. Each entry of the code book consists of a color difference, its frequency,and a corresponding code word,which are denoted by d x,f x and w x,respectively(1≤x≤X).The last entry in the code book is the frequency and code word for the remaining pixels which are not reprented by crit-ical color differences.The compression rate of differential Huffman coding with a limited-size code book is calculated as
R=
nV S+∑X x=1l x f x+(l o+n)f o
nV S H S
,(3) where l x denotes the length of a code word for pixels with a critical color difference,and l o denotes the length of the
Critical color
diffs.
Other pixels
Figure 2羊排汤的做法
.X -entry limited code book for differential Huff-man coding with a limited-size code book.
(c)Pixel without a critical color difference
Figure 3.Pixel coding with a limited-size code book.
prefix code for the other pixels.The first,cond and third terms correspond to the length of encoded pixels as shown in Fig.3(a),(b)and (c),respectively.
We must lect a good t of critical color differences,becau the compression performance depends on their quality.We u a P -entry color-difference table to lect X critical color differences (P ≥X ).As shown in Fig.4,each entry of the table consists of d p ,f p and t p ,which denote a color difference,a frequency and a time stamp,respectively (1≤p ≤P ).
During a first refresh period,we lect only 32critical color differences (X =32in Fig.2)using a 64-entry color-difference table (P =64in Fig.4).We u a LRFU (least recently and frequently ud)replacement policy with the replacement ratio (R R )of 1%when we are forced,becau of the limited number of entries in the table,to choo an entry to be replaced with a new color difference.Having decided on a t of 32critical color differences,we profile them against the contents of the frame buffer once more,so as to build an accurate statistical model of the color differ-ences during a cond refresh period.At the end of the c-ond refr喝饮料的英文
esh period,the Huffman codes are generated during an idle period (backporch and frontporch)between concu-tive refresh
operations,and a code book is constructed.Dur-ing a third refresh period,actual frame buffer compression can be conducted using the new code book.
Figure 4.P -entry color-difference table ud to lect critical color differences.
First refresh period:
Input :Pixel color data (C i ,j )and color-difference table
(d 1,...,d P ,f 1,...,f P and t 1,...,t P ).Output :Critical color differences (d 1,...,d X ).At the beginning of a refresh period
For each p of 1≤p ≤P in the color-difference table f p =0;End for ;
During a refresh period
For each j of 1≤j ≤V S on the screen For each i of 2≤i ≤H S on the screen
If there exists an h -th entry,for which d h =C i ,j and f h =0,in the table Then t h =i +jH S ;f h =f h +1;
El if there exists an e -th entry,for which f e =0,in the table Then
d e =C i ,j ;t e =i +jH S ;f e =1;El
Select all the entries for which f p <R R (i +jH S )in the table;
Choo the r -th entry who t r is less than any other among them;
d r =C i ,j ;t r =i +jH S ;f r =1;End if ;End for ;End for ;
At the end of a refresh period
Select X critical color differences among the P entries in the table;
Second refresh pericad如何倒角
od:
Input :Pixel color data (C i ,j )and critical color differences (d 1,...,d X ).
Output :Code book (f 1,...,f X ,f o ,w 1,...,w X and w o ).At the beginning of a refresh period
For each x of 1≤x ≤X in the code book
Initialize d x with a lected critical color difference;f x =0;End for ;f o =0;
During a refresh period
For each j of 1≤j ≤V S on the screen For each i of 2≤i ≤H S on the screen
If there exists an h -th entry,for which d h =C i ,j Then f h =f h +1;El
f o =f o +1;End if ;End for ;End for ;
At the end of a refresh period
For each x of 1≤x ≤X in the code book Construct a symbol who frequency is f x ;End for ;
Construct a symbol who frequency is f o ;
Generate the Huffman codes (w 1,...,w X and w o )for X +1symbols;
Fill the code book with the new code words;Third refresh period:
Input :Pixel color data (C i ,j )and Code book
(d 1,...,d X ,f 1,...,f X ,f o ,w 1,...,w X and w o ).Output :Compresd pixel data.During a refresh period
For each j of 1≤j ≤V S on the screen For each i of 1≤i ≤H S on the screen If i =1Then
Encode the pixel as shown in Fig.3(a);
El if there exists an h -th entry,for which d h =C i ,j Then
Encode the pixel as shown in Fig.3(b);El
Encode the pixel as shown in Fig.3(c);End if ;End for ;End for ;
Figure 5.Triple-pass differential Huffman coding algo-rithm with a limited-size code book.
Table3.Selected critical color differences(d1,...,d X)in the Photoshop application.
d x Freq.d x Freq.
x
(C R,C G,C B)(%)x(C R,C G,C B)(%)
1(0,0,0)37.38(0,1,1) 2.1
2(31,31,31) 4.19(0,1,0) 2.1
3(1,1,1) 4.010(0,31,0) 2.0
4(0,0,1) 2.711(0,31,31) 2.0
5(0,0,31) 2.612(1,1,0) 1.7
6(1,0,0) 2.413(31,31,0) 1.7
7(31,0,0)
A complete triple-pass differential Huffman coding algo-rithm with a limited-size code book is described in Fig.5. Frame buffer compression is not a single-pass algorithm, and therefore it is performed in a3-stage pipeline by the compression logic embedded in the LCD controller.Table 2shows that differential Huffman coding with a limited-size code book exhibits more robust performance than adaptive RLE,since its compression rate is lower than50%for all the MobileMark2002applications.
2.6Color-difference reduction
Although differential Huffman coding with a limited-size code book us only a small number of entries in the color-difference table and the code book,its compression logic is more complex than adaptive RLE,since the encoder(e Fig.1)needs to embed two kinds of CAM(content address-able memory):a P-entry CAM for the color-difference table and an X-entry CAM for the code book.Huffman coding requires an accurate statistical model for the color differ-ences.Therefore,if we could we would increa the size of the CAMs to obtain better compression performance. However,the size of the CAMs is directly related to the im-plementation costs such as the area of silicon and its power consumption,and thus we propo techniques to reduce the size of the CAMs.
First,we replace any negative color-difference compo-nent value with a positive value by adding2n/3to it in both the P-entry and the X-entry CAMs.A color difference con-sists of three color-difference components,C R,C G and C B, and they range from-31to31(25−1)in a16-bpp frame buffer.For example,the eight color differences(1,1,1),(1, 1,-31),(1,-31,1),(1,-31,-31),(-31,1,1),(-31,1,-31), (-31,-31,1)and(-31,-31,-31)can be merged into a sin-gle color difference of(1,1,1).Table3shows the critical color differences that are lected for the Photoshop appli-cation using our algorithm(e thefirst pass of Fig.5)and this reduction technique.Second,we assume symm
etry in color differences,and u it to reduce the size of the P-entry CAM.In Table3,each color difference has its counterpart such as(d2,d3),(d4,d5)and(d6,d7).More precily,color di提高阅读速度的方法
fferences of(C R,C G,C B)and(2n/3−C R,2n/3−C G, 2n/3−C B)appear with almost the same frequency on the screen,and therefore there is no need to count each of them parately.Should symmetry in color differences turns out to be abnt,we will have a bad code book with about a half number color differences wrong.This would lead to de-graded compression performance,but the compresd data would still be correct.
Note that the two reduction techniques decrea the number of possible color differences by1/16and thus re-duce the size of the CAMs by1/2,while achieving the same compression performance.
20
40
60
80
C
o
m
p
r
e
s
s
i
o
n
r
a
t
e
(
%
)
Screen updates
Compression rate using the initial code book continuously
Compression rate changing to the newly generated code book
every refresh period
Figure6.Compression rate using the initial code book and the newly generated code book,in differential Huff-man coding with a limited-size code book(P=64and X=32).
2.7Adaptive code book update
The frame buffer compression logic using differential Huff-man coding must decide whether or not to update the cur-rent code book with a new one becau the cond pass of the propod algorithm generates a new code book that corresponds to the image on the screen at the end of ev-ery refresh period.If the code book is updated,we must re-compress the whole frame buffer contents using the new code book and it consumes significant power.Fortunately, the contents of the code book show a strong tendency to stay relatively constant while a ur is working in a single application.It is the ca even when the ur is watching a movie due to temporal correlations in the frame buffer contents.But,if the ur switches to a new application, the code book should be updated,becau a new window with a different color context will be brought to the front of the screen and the current code book will no longer achieve good compression.
Fig.6shows the changes in the compression rate achieved when we continue to u the initial code book generated at the beginning of the Photoshop application, and when we update the code book every refresh period, respectively.The Photoshop application takes5minutes and57screen updates occur during its execution in the Mo-bileMark2002benchmark.Although Photoshop us more color differences than any other benchmark applications, using the same code book has little effect on its compres-sion performance.But,when the ur switches to the Flash application(at the58-th screen update)the performance be-comes noticeably wor.This is the right time to update the code book to save more energy,even though the code book update involves re-compression of the whole frame buffer contents.
Generally,the penalty for not updating the code book is the degraded compression performance,which is less than 3%of the compression rate in a single application.Our compression logic,using a limited-size code book,man-ages both the current code book and the new code book, and us Eq.3to derive the appropriate compression rates from them.Our adaptive scheme updates the code book only when the degraded compression performance exceeds 3%of the compression rate by comparing the two com-pression rates.
3.Performance analysis
3.1Compression performance
An incremental re-compression scheme[7]has been intro-duced to accommodate frequent partial frame buffer up-
dates.It divides the screen into veral zones both horizon-tally and vertically.Previous work does not analyze the way in which the horizontal zone size affects the compression performance,and thus we perform a mathematical analysis of this effect.
In differential Huffman coding with a limited-size code book,the average length of the code words,m ,for V S (H S −1)pixel color differences on the screen,is given by
m =∑X
x =1
l x f x +(l o +n )f o V S (H S −1)
.(4)In the incremental re-compression scheme,the compression rate with a horizontal zone size of H Z is estimated as
R H Z =nV S H S /H Z +mV S (H S −H S /H Z )nV S H S
.(5)
Since m /n is almost equal to R from Eqs.3and 4due to H S 1,we can approximate Eq.5as
R H Z ≈(1−1H Z )R +1
H Z
.(6)
We now introduce the concept of the effective compres-sion rate which is bad on the number of frame buffer ac-cess rather than on the size of the image data stored in the frame buffer.Previous work using the compression rate rather than the effective compression rate,suggests some-what over-optimistic compression performance becau the compression向日葵怎么养
rate is always lower than the effective com-pression rate.The number of frame buffer access during a refresh period in the incremental compression scheme with a horizontal zone size of H Z is calculated as
N H Z c f b =R H Z e f f N f b =
V S ∑
j =1H S
H Z
∑k =1
R k j H Z
L f b
,(7)
where
R H Z
e f f
denotes the effective compression rate,and R k j denotes the compression rate for the k -th gment
of the j -th line on the screen.The effective compression rate is always higher than the compression rate since the decom-pression logic (the decoder in Fig.1)access compresd pages in the frame buffer using a fixed-length burst trans-fer and is therefore prone to prefetch unnecessary data for decompression.Table 4shows the actual effective compres-sion rate in each application when the horizontal zone size increas from 32to 640pixels,when frame buffer access take place in 8-pixel bursts (L f b =8).
The difference between the effective compression rate and the compression rate can be calculated as
N f b (R H Z
e f f −R H Z )=
V S ∑j =1H S
H Z
∑k =1
(
R k j H Z L f b −R k j H Z L f b )≈V S H S
2H Z .(8)
From Eqs.1,6and 8,we can then estimate the effective compression rate as
R H Z
e f f
≈R H Z +L f b 2H Z =(1−1H Z )R +L f b +22H Z
.(9)This analysis of the effect of the horizontal zone size vari-ations on the effective compression rate shows an average 0.1%error,when we compare the estimated effective com-pression rate with the actual value shown in Table 4.Instead of the compression rate,the effective compression rate must be ud to calculate the reduced frame buffer activity in the incremental re-compression scheme,becau the difference between the two rates increas noticeably as the horizontal zone size decreas (e Table 4).
Table 4.The effective compression rates (R H
Z e f f )using dif-ferential Huffman coding with a limited-size code book
for the different horizontal zone sizes in the incremental re-compression scheme (%).
H Z (pixels)3264128320640Photoshop 61.4454.1150.6448.4147.79Flash 53.2743.8641.3539.7739.14Word 26.3516.5014.4911.1210.26Excel 27.2317.5815.6912.9812.15PowerPoint 43.0435.1531.8729.2028.48Slide show 40.9834.4330.9928.3527.63Outlook 31.7821.3719.3816.0615.54Communicator 35.5825.6823.3520.7919.88
3.2Energy reduction
The energy saving results from the reduced number of frame buffer access and画天安门
it is achieved only if a sweep op-eration us a compresd page instead of a decompresd page.The frame buffer is configured to operate at 100MHz with two Samsung K4S561632A-TC/L75SDRAM chips for 32-bit data bus width.The LCD controller access the frame buffer using a 4-beat burst transfer (8pixels with a color depth of 16bpp).We have measured the energy con-sumption of the frame buffer for each read and write access.The frame buffer consumes 40.21nJ/access (E f br )for a read access and 30.68nJ/access (E f bw )for a write access.Thus,energy saving for each refresh period due to fra
me buffer compression,with the incremental re-compression scheme is calculated as
E H Z S =E f br (N f b −N H Z c f b )=E f br N f b (1−R H Z
e f f )(1−P H Z e f f ),
(10)
where P H Z
e f f denotes the effective proportion of updated zones ,which is determined by the ratio of the number of the updated zones over the total number of zones on the screen during a refresh period.
The energy overhead to re-compress the updated zones during a refresh period is calculated as
E H Z O =E f bw N f b R H Z
e f f P H Z e f f ,
(11)
and the overall energy reduction can be calculated by sub-tracting the energy overhead from the energy saving.To
maximize the energy reduction using the incremental re-compression scheme,the compression logic must change the horizontal zone size to suit the current screen image and screen update behavior.Static exploration to find out the energy-optimal horizontal zone sizes for the various appli-cations is reported in our previous work [7].
4.Experimental Results
4.1Implementation
We have implemented an LCD controller with a Xilinx Virtex-II XC2V1000-FG456FPGA,which integrates our frame buffer compression scheme using differential Huff-man coding with a limited-size code book.The prototype shown in Fig.7has parate power planes to measure the power consumption of each component such as an SDRAM frame buffer memory and an FPGA LCD controller.We borrowed veral IP cores such as a PCI interface,FIFOs,CAMs,multipliers,and dividers from Xilinx.The imple-mented controller occupies 1,372slices,with an equivalent
