jpeg 编解码在 cell 上的优化.htm

一个jpeg的解码库

            width=565> <BR>
            <P>planarToInterleaved这一步指的是将Y、Cb、Cr分开的几段buffer，经过颜色转化后，存储为BGR间隔排列的一段buffer，最后这段buffer会被写入bmp文件，如图3所示：</P><BR><A 
            name=N100F5><B>图3：planarToInterleaved 过程</B></A><BR><IMG height=200 
            alt="planarToInterleaved 过程" 
            src="JPEG 编解码在 Cell 上的优化.files/image003.gif" width=552> <BR>
            <P>具体的JPEG编解码原理见 <A 
            href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#resources">参考资料</A>。</P><BR>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD><IMG height=1 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/blue_rule.gif" 
                  width="100%"><BR><IMG height=6 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/c.gif" width=8 
              border=0></TD></TR></TBODY></TABLE>
            <TABLE class=no-print cellSpacing=0 cellPadding=0 align=right>
              <TBODY>
              <TR align=right>
                <TD><IMG height=4 alt="" src="JPEG 编解码在 Cell 上的优化.files/c.gif" 
                  width="100%"><BR>
                  <TABLE cellSpacing=0 cellPadding=0 border=0>
                    <TBODY>
                    <TR>
                      <TD vAlign=center><IMG height=16 alt="" 
                        src="JPEG 编解码在 Cell 上的优化.files/u_bold.gif" width=16 
                        border=0><BR></TD>
                      <TD vAlign=top align=right><A class=fbox 
                        href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#main"><B>回页首</B></A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><BR>
            <P><A name=N10108><SPAN class=atitle>程序移植</SPAN></A></P>
            <OL>
              <LI>使程序在PPU上正常运行起来。一般来说，适用于x86的源代码，如果在Linux上可以正常运行的话，移植到Cell上基本不需要太多的改动的。但是，因为x86平台是little-endian存储数据的，Cell平台是big-endian的，所以在程序中如果有字节位操作的话，需要做些修改。 

              <LI>考虑整个程序流程中，哪些部分适合在PPU上执行，哪些部分适合在SPU上执行。我们将文件的读取和写入在PPU上执行，PPU获取到文件buffer和大小后通知SPU，然后由SPU完成编解码过程并将结果buffer写回主存，最后由PPU来写入文件。 

              <LI>考虑程序是否能够放在只有256K内存的SPU上，如果程序代码量太大，要精简代码或者考虑使用overlay技术。我们初始的源代码具备很多功能，可以做图片的切割、伸缩、颜色分离等等，为了能够移植到SPU上运行，我们将代码精简为处理较为单一的功能，从而最小化代码大小。 

              <LI>考虑处理的单元块大小是否合适。我们使用的原始代码每次处理的单元块为一个MCU行，和图像的宽度有关。这样，当图片很宽的时候，程序大小会超出256K的限制。所以，我们修改了每次的处理单元块，横向是固定的象素点（而不是和图像的宽度有关），纵向是一个MCU的行数。 

              <LI>考虑采用何种通信机制。PPU通过signal机制通知SPU开始JPEG编解码；SPU通过中断mailbox机制通知PPU其编解码结束。 
              </LI></OL><BR><A name=N10121><B>图4：在 Cell 上运行的 JPEG 
            编解码过程</B></A><BR><IMG height=229 alt="在 Cell 上运行的 JPEG 编解码过程" 
            src="JPEG 编解码在 Cell 上的优化.files/image004.gif" width=553> <BR><BR>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD><IMG height=1 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/blue_rule.gif" 
                  width="100%"><BR><IMG height=6 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/c.gif" width=8 
              border=0></TD></TR></TBODY></TABLE>
            <TABLE class=no-print cellSpacing=0 cellPadding=0 align=right>
              <TBODY>
              <TR align=right>
                <TD><IMG height=4 alt="" src="JPEG 编解码在 Cell 上的优化.files/c.gif" 
                  width="100%"><BR>
                  <TABLE cellSpacing=0 cellPadding=0 border=0>
                    <TBODY>
                    <TR>
                      <TD vAlign=center><IMG height=16 alt="" 
                        src="JPEG 编解码在 Cell 上的优化.files/u_bold.gif" width=16 
                        border=0><BR></TD>
                      <TD vAlign=top align=right><A class=fbox 
                        href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#main"><B>回页首</B></A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><BR>
            <P><A name=N1012D><SPAN class=atitle>性能分析</SPAN></A></P>
            <P>整个程序的主要部分移植到SPU上后，需要分析目前性能的瓶颈在哪儿，然后开始做具体的优化工作。</P>
            <P>我们在程序的各个部分中添加prof_clean、prof_start和prof_stop，使用mambo来分别测出各个部分的CPU 
            cycle数及整个编解码过程的总CPU cycle数（具体操作步骤见 <A 
            href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#resources">参考资料</A>），这样就可以知道各个部分在整个编解码过程中所占的cycle数比率。</P>
            <P>我们刚开始性能分析的结果表明，图1和图2所示的4个部分所占用的cycle数比率加在一起约等于100%，这4个部分就成为我们主要的观察范围。其中，FDCT和IDCT占用最多的cycle数比率，超过了50%。找到瓶颈所在后，再对这个部分做具体的性能分析，由mambo的结果找出不合理的cycle是branch 
            miss、dependency还是channel stall，然后针对性的进行优化。</P>
            <P>在不断的性能优化中，需要不断地重新用mambo来做性能分析，因为可能开始的时候某个部分是瓶颈，然后优化完这个部分，另外一个部分会成为瓶颈。我们将FDCT和IDCT做完优化后，其所占的cycle比率降为30％左右，而huffman部分cycle比率变高，成为我们优化的焦点；到后来，bitmapOutput和bitmapInput部分也出现比率较高的channel 
            stall，我们优化了其DMA部分。</P>
            <P>总之，在Cell平台上的程序性能优化，需要以性能分析的结果作为优化的依据。</P><BR>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD><IMG height=1 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/blue_rule.gif" 
                  width="100%"><BR><IMG height=6 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/c.gif" width=8 
              border=0></TD></TR></TBODY></TABLE>
            <TABLE class=no-print cellSpacing=0 cellPadding=0 align=right>
              <TBODY>
              <TR align=right>
                <TD><IMG height=4 alt="" src="JPEG 编解码在 Cell 上的优化.files/c.gif" 
                  width="100%"><BR>
                  <TABLE cellSpacing=0 cellPadding=0 border=0>
                    <TBODY>
                    <TR>
                      <TD vAlign=center><IMG height=16 alt="" 
                        src="JPEG 编解码在 Cell 上的优化.files/u_bold.gif" width=16 
                        border=0><BR></TD>
                      <TD vAlign=top align=right><A class=fbox 
                        href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#main"><B>回页首</B></A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><BR>
            <P><A name=N10145><SPAN class=atitle>SPU 上的优化</SPAN></A></P>
            <P>我们用到的优化方式主要有如下几点：</P>
            <OL>
              <LI>SIMD 
              <LI>减小branch miss和dependency 
              <LI>double-buffering和multi-buffering </LI></OL>
            <P><A name=N10159><SPAN class=smalltitle>SIMD</SPAN></A></P>
            <P>一般来说，算法比较规则、数据之间依赖性较小的部分容易做SIMD，我们主要在以下几个方面做了SIMD优化：</P>
            <P><B>1． IDCT的SIMD：</B> </P>
            <P>IDCT算法比较规则，适合做SIMD的优化，具体SIMD过程如图5所示。</P>
            <P>步骤一：左上角的数据是输入数据，为8x8的矩阵，按照上四行和下四行分为两部分，分别放入两组向量中去。注意，这一步骤中，向量的元素在内存中并不连续，因此需要对原始数据进行转置，这个转置的操作可以在进行反量化的同时进行，这样就不需要额外再操作一次。</P>
            <P>步骤二：完成向量的提取后，分别对上半部和下半部向量组进行1维DCT变换（完成行变换），得到右上角的中间矩阵(v，bv)。 
            因为每个向量中存放四个元素，一次运算可以得到四行的结果。再对中间矩阵按照左半部和右半部得到的两个向量组cv和rcv，分别为左半部和右半部的向量。这个过程，也就是由(v，bv)得到(cv，rcv)，等效于进行了转置操作，可以利用如下程序片断，较高效地完成这一操作，不需要任何写回内存的操作。</P>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD class=code-outline><PRE class=displaycode>register vector unsigned char hi = (vector unsigned char){
0x00,0x01,0x02,0x03,0x10,0x11,0x12,0x13,0x04,0x05,0x06,0x07,0x14,0x15,0x16,0x17
};
register vector unsigned char lo = (vector unsigned char){
0x08,0x09,0x0A,0x0B,0x18,0x19,0x1A,0x1B,0x0C,0x0D,0x0E,0x0F,0x1C,0x1D,0x1E,0x1F
};
tempV = spu_shuffle(v0, v2, hi);
tempV_1 = spu_shuffle(v0, v2, lo);
tempV_2 = spu_shuffle(v1, v3, hi);
tempV_3 = spu_shuffle(v1, v3, lo);
cv0 = spu_shuffle(tempV, tempV_2, hi);
cv1 = spu_shuffle(tempV, tempV_2, lo);
cv2 = spu_shuffle(tempV_1, tempV_3, hi);
cv3 = spu_shuffle(tempV_1, tempV_3, lo);
</PRE></TD></TR></TBODY></TABLE><BR>
            <P>对这两组向量(cv，rcv)再进行1维DCT变换（完成列变换），得到最后的变换结果。</P>
            <P>步骤三：步骤二中得到的结果向量，每个向量中只包含四个字节的有效数据，直接存储到内存中去会比较低效，因此将一行中相邻的8个字节压缩到一个向量中去，再进行后续的操作会更高效。</P>
            <P>步骤四：将向量依次写入内存。</P><BR><A name=N10180><B>图5：IDCT 的 
            SIMD</B></A><BR><IMG height=521 alt="IDCT 的 SIMD" 
            src="JPEG 编解码在 Cell 上的优化.files/image005.jpg" width=498> <BR>
            <P><B>2． FDCT的SIMD：</B> </P>
            <P>FDCT算法是IDCT的逆算法，SIMD的过程也基本是IDCT的逆过程。所不同之处是，对于IDCT而言，输入数据来自于Huffman解码后的数据，需要反量化处理后才能进行运算，运算完成后得到的就是颜色空间中的数据了，一般就是YCbCr分量的值；而对于FDCT来说，输入来自于YCbCr的原始数据，输出则需要进行量化运算。考虑到量化运算本身也具有一定的计算复杂度，IDCT与FDCT在起始部分与结尾部分向量的处理要有所区别。</P>
            <P><B>3． bitmapInput的SIMD：</B> </P>
            <P>bitmapInput在JPEG的编码过程中实现了颜色转换（数据从BGR色系到YCbCr色系）和数据分离（将BGR排列的数据转化为Y、Cb、Cr分开的数据，便于做后面的FDCT），其具体SIMD过程如图6所示：</P><BR><A 
            name=N101A0><B>图6：bitmapInput 的 SIMD</B></A><BR><IMG height=396 
            alt="bitmapInput 的 SIMD" 
            src="JPEG 编解码在 Cell 上的优化.files/image006.gif" width=572> <BR>
            <P><B>4． planarToInterleaved的SIMD：</B> </P>
            <P>planarToInterleaved在JPEG的解码过程中实现了颜色转换（数据从YCbCr色系到BGR色系）和数据组合（将Y、Cb、Cr分开的数据组合为BGR排列的数据，最后写到bmp格式的文件中），其具体SIMD过程如图7所示：</P><BR><A 
            name=N101B7><B>图7：planarToInterleaved 的 SIMD</B></A><BR><IMG 
            height=390 alt="planarToInterleaved 的 SIMD" 
            src="JPEG 编解码在 Cell 上的优化.files/image007.gif" width=565> <BR>
            <P><A name=N101C3><SPAN class=smalltitle>减小 branch miss 和 
            dependency</SPAN></A></P>
            <P>在各个部分的CPU cycle结果中，当branch 
            miss和dependency的cycle超过20%比率的时候，就应该考虑减小branch 
            miss和dependency，，我们主要在以下几个方面做了优化：</P>
            <P><B>1． huffmanDecoder</B> </P>
            <P>解码过程中需要判别是否为0xFF的字节，然后忽略紧随的0x00。假定JPEG文件的数据区域段中0xFF均为实际的图像数据，可以进行如此优化：对于压缩过的bit流，每次提取64个bits到一个vector中，64个bit是8个bytes，因此用一个256个单元的表就可以表示0xFF的分布状况，可以先计算出这样一个表，再利用向量运算直接查表即可完成对0xFF的处理。这样可以完全消除其过程中的判断语句，从而减小branch 
            miss。</P>
            <P><B>2． 其他减小branch miss的方法：</B> </P>
            <P>我们在头文件中定义了如下的宏来做branch hint：</P><PRE>#define unlikely(_c) __builtin_expect((_c), 0)
#define likely(_c) __builtin_expect((_c), 1)
</PRE>
            <P>然后，将所有的判断返回值错误的地方，如下代码：</P><PRE>if( returnCode != 0 )
{
        return returnCode;
}
</PRE>
            <P>改为：</P><PRE>if( unlikely(returnCode != 0) )
{
    	return returnCode;
}
</PRE>
            <P>当某个条件大多数时候总是成立的时候，则使用likely来做branch hint。</P>
            <P><A name=N101F0><SPAN class=smalltitle>double-buffering 和 
            multi-buffering</SPAN></A></P>
            <P>当性能测试的结果表明，channel的cycle比率较高的时候，需要考虑double-buffering或者multi-buffering。这时候，程序的数据DMA传输时间大于数据处理时间，需要减小等待数据DMA的时间。double-buffering是multi-buffering的一种形式，当使用两段buffer的时候，称为double-buffering。我们主要在如下几个方面做了multi-buffering的处理：</P>
            <P><B>1． bitmapInput的double-buffering：</B> </P>
            <P>bitmapInput在JPEG的编码过程中实现了bmp图片的数据DMA读取，其double-buffering过程如图 8 
            所示：</P><BR><A name=N10204><B>图8：bitmapInput 的 
            double-buffering</B></A><BR><IMG height=308 
            alt="bitmapInput 的 double-buffering" 
            src="JPEG 编解码在 Cell 上的优化.files/image08.gif" width=554> <BR>
            <P><B>2． bitmapOutput的multi-buffering：</B> </P>
            <P>bitmapOutput在JPEG的解码过程中实现了bmp图片的数据DMA写出，其multi-buffering过程和double-buffering基本相似。DMA写出的时候，分配了更多的buffer作为数据的写出缓冲，其过程如图9所示：</P><BR><A 
            name=N1021B><B>图9：bitmapOutput 的 multi-buffering</B></A><BR><IMG 
            height=279 alt="bitmapOutput 的 multi-buffering" 
            src="JPEG 编解码在 Cell 上的优化.files/image09.gif" width=553> <BR><BR>
            <TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
              <TBODY>
              <TR>
                <TD><IMG height=1 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/blue_rule.gif" 
                  width="100%"><BR><IMG height=6 alt="" 
                  src="JPEG 编解码在 Cell 上的优化.files/c.gif" width=8 
              border=0></TD></TR></TBODY></TABLE>
            <TABLE class=no-print cellSpacing=0 cellPadding=0 align=right>
              <TBODY>
              <TR align=right>
                <TD><IMG height=4 alt="" src="JPEG 编解码在 Cell 上的优化.files/c.gif" 
                  width="100%"><BR>
                  <TABLE cellSpacing=0 cellPadding=0 border=0>
                    <TBODY>
                    <TR>
                      <TD vAlign=center><IMG height=16 alt="" 
                        src="JPEG 编解码在 Cell 上的优化.files/u_bold.gif" width=16 
                        border=0><BR></TD>
                      <TD vAlign=top align=right><A class=fbox 
                        href="http://www.ibm.com/developerworks/cn/linux/l-cn-celljpegopt/#main"><B>回页首</B></A></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE><BR><BR>
            <P><A name=N10227><SPAN class=atitle>结果分析</SPAN></A></P>
            <P>经过上述几个方面在SPU上的优化，和最初移植到Cell上的代码相比，JPEG的编解码性能提高很大，JPEG编码在一个SPU上优化的情况如图10所示，JPEG解码在一个SPU上优化的情况如图11所示：</P><BR><A 
            name=N10231><B>图10：JPEG 编码优化代码和原始代码性能相比</B></A><BR><IMG height=222 
            alt="JPEG 编码优化代码和原始代码性能相比" 
            src="JPEG 编解码在 Cell 上的优化.files/image010.gif" width=558> <BR><BR><A 
            name=N1023F><B>图11：JPEG 解码优化代码和原始代码性能相比</B></A><BR><IMG height=282 
            alt="JPEG 解码优化代码和原始代码性能相比" 
            src="JPEG 编解码在 Cell 上的优化.files/image011.gif" width=552> <BR>
            <P>由此可见，移植到Cell上的代码需要做一些特定的优化（特别是SIMD）后，才能达到较好的性能。</P>
            <P>JPEG编码在一个SPU上达到的性能及cycel分布（由mambo测得）如表1所示，JPEG解码在一个SPU上达到的性能及cycel分布如表2所示：</P><BR><A 
            name=N10253><B>表1：JPEG编码在一个SPU上的性能</B></A><BR><IMG height=198