• Home
• Descriptor
• Announcements
• Schedule and Notes
• Assignments
• Feedback
• Sponsors

• View
• Print
• Logout ()
• Login

Parallelism and Locality in CELL processor using Sequoia compiler

Part1: Out: 11/6/2008 Due:11/13/2008

Part 2: Out: 11/6/2008 Due:11/18/2008

Part 3: Out: 11/6/2008 Due:11/21/2008

This lab has two main goals. The first is to introduce you to CELL architecture to give you a feel for stream programming. You will understand some of the capabilities and limitations of this processor. The second goal is to introduce you to SEQUOIA compiler, a programming language that is designed to facilitate the development of memory hierarchy aware parallel programs that remain portable across modern machines with different memory hierarchy configurations.

To achieve these goals we will look at another basic construct — vector convolution. Specifically, we will write a 1D-Fast Wavelet Compression application that is a common application in any signal and image processing.

You will implement your algorithm on a Play Station 3 game box (don’t worry you do not need to have game pads). PS3 uses CELL processor but only 6 out 8 SPEs are usable.

What are Wavelets?

The most basic definition of a wavelet is simply a function with a well defined temporal support that “wiggles” about the X-axis (it has exactly the same area above and below the axis).

This definition however does not help us much, and a better approach is to explain what the wavelet transform and wavelet analysis are.

The basic Wavelet Transform is similar to the well known Fourier Transform. Like the Fourier Transform, the coefficients are calculated by an inner-product of the input signal with a set of orthonormal basis functions that span R¹ (this is a small subset of all available wavelet transforms though). The difference comes in the way these functions are constructed, and more importantly in the types of analysis they allow.

The key difference is that the Wavelet Transform is a multi-resolution transform, that is, it allows a form of time—frequency analysis (or translation—scale in wavelet speak). When using the Fourier Transform the result is a very precise analysis of the frequencies contained in the signal, but no information on when those frequencies occurred. In the wavelet transform we get information about when certain features occurred, and about the scale characteristics of the signal. Scale is analogous to frequency, and is a measure of the amount of detail in the signal. scale generally means coarse details, and large scale means fine details (scale is a number related to the number of coefficients and is therefore counter-intuitive to the level of detail).

The Discrete Wavelet Transform can be described as a series of filtering and sub-sampling (decimating in time) as depicted below. In each level in this series, a set of 2 ^j-1 coefficients are calculated, where j<J is the scale and N=2 ^j is the number of samples in the input signal. The coefficients are calculated by applying a high-pass wavelet filter to the signal and down-sampling the result by a factor of 2. At the same level, a low-pass scale filtering is also performed (followed by down-sampling) to produce the signal for the next level. Both the wavelet and scale filters can be obtained from a single Quadrature Mirror Filter (QMF) function that defines the wavelet.

Each set of scale-coefficient corresponds to a “smoothing” of the signal and the removal of details, whereas the wavelet-coefficients correspond to the “differences” between the scales. Wavelet theory shows that from the coarsest scale-coefficients and the series of the wavelet-coefficients the original signal can be reconstructed. The total number of coefficients (scale + wavelet) equals the number of samples in the signal.

Wavelet Compression

How do we use these transform coefficients to perform compression? The distribution of values for the wavelet coefficients is usually centered around 0, with very few large coefficients. This means that almost all the information is concentrated in a small fraction of the coefficients and can be efficiently compressed. This is done by quantizing the values based on the histogram and encoding the result in an efficient way, e.g. Huffman Encoding. For this homework we will use a simpler method, and instead of quantizing we will discard all but the M largest coefficients. This provides a compression ratio of roughly 2M/N (the factor of 2 is for storing both the coefficient value and index).

Where to Get More Information

A very good book on wavelets is A Wavelet Tour of Signal Processing, 2nd edition’ by Stephane Mallat.

There are several reasonable tutorials on the web such as: http://perso.wanadoo.fr/polyvalens/clemens/wavelets/wavelets.html

The MATLAB Wavelet toolbox user guide is a very good source with various examples and figures that can help you understand the concept easier. You can read chapter 1 to get the concept and review the advanced concepts in chapter 6 Fast Wavelet Transform is declared in 6- 20. Here is the Link: http://www.mathworks.com/access/helpdesk/help/pdf_doc/wavelet/wavelet_ug.pdf Algorithm Description

Compression Algorithm

The compression algorithm has two parts. The first is a wavelet transform that uses the Fast Wavelet Transform. After calculating the transform coefficients a sort is applied, and all but the largest n coefficients are discarded. The signal can be reconstructed by performing an Inverse Wavelet Transform using the n stored coefficients and zeroing out all other coefficients.

I will now describe in more detail the simplest wavelet transform which is an orthogonal and periodic transform.

The pseudo code for the Fast Wavelet Transform algorithm appears below. The algorithm consists of a main loop that has two parts. This first part calculates the wavelet coefficients in the current scale (high-pass filter), and the second part calculates the scale coefficients by low-pass filtering and essentially shifts the scale down (towards less details). This loop is repeated ‘O(log n)’ times, once for each scale. Notice that the amount of computation in each iterations shrinks by a factor of two for each scale lowered. As a result the total computation cost is ‘O(n)’, and the filter is applied to roughly 4n elements.

Both the low-pass and high-pass filtering are performed on a periodically padded version of the current-scale signal {$\phi_j(n)$}, and the result is decimated by 2. The filter kernels define the wavelet and are computed from its characteristic QMF.

Fast Wavelet Transform Pseudo code

I’ve used some Matlab like notation:

1. Arrays are indexed from 1 to their length instead of 0- (length - 1)
2. x(start:end) means all elements of x from start index to end index
3. [x y] mean concatenate y to x
4. x + 1 means add 1 to all elements of x
5. [start:end] is a vector which includes all numbers from start to end
6. x(y) - a vector of elements of x with indices y
7. [start:stride:end] a vector from start to end with a constant stride; [1:2:10] = [1 3 5 7 9]

What You Have to Do

The assignment will have four steps, and we would like you to inform us of your progress:

• Part 1 - Fast Wavelet transform Mapping and Sequoia draft 11/13
• Part 2 - Make the FWT work on PS3 and Integrate the transform with a provided sort routine. 11/18
• Part 3 - Optimize the Mapping file
• Part 3(B) - Optimize the Leaf Task 11/21.

Step 0

Just preliminary setup operations:

Set up the Sequoia environment. Here is the Sequoia web page:
http://www.stanford.edu/group/sequoia/cgi-bin/node/8
You can find the related Sequoia Documents and papers there.
http://www.stanford.edu/group/sequoia/cgi-bin/node/17

There are currently two PS3 systems available for you. Fedora core 6 and CELL SDK are already installed on them. You have to install Sequoia for your users and set the paths. You can access these systems remotely with ssh to dali.ece.utexas.edu with port 22 for the first PS3(dali) and with port 23 for second PS3 (slavador)

• PATH needs to include $HOME/sequoia/bin/PPC
• SQ_RT_DIR needs to be set to $HOME/sequoia/runtime

Test the environment by compiling and running one of the demo applications. The following examples work on the PS3:

• histogram
• conv1d_ichop
• conv2d
• vectadd
• saxpy
• sgemv

Some of the other examples may not work.

• note that the VectAdd is the easiest application that you can play with.
• You should go and modify the Makefile in each example and make it use the mapping_ps3.xml because there are only 6 SPEs available on the PS3.
• You should also take a look at Convolution examples provided there because those topics are related to the Wavelet transform.

OVERVIEW (What is going on in a Sequoia Program)

For your Information

Please read this brief introduction to become familiar with how things work. In this Lab there are more than 6 different files that codes for them have to be written .

• Sequoia Part :

1. FWT.sq
2. mapping_ps3.xml
3. FWT.h

• CPU part :

1. ref_FWT.h
2. ref_FWT.c

• Interface :

1. main.cc

• Optimization files:
  • for different optimizations you may need to write different mapping files and compare their results

1-FWT.sq : is the Sequoia source code which contains the inner and leaf function calls for your algorithm.
2-mapping_ps3.xml : is the XML format mapping file for ps3 which maps your Sequoia source code for target machine which is PS3 here. In this file you can also set different optimization options.
3-FWT.h : is a simple file in which your parameters are set.
4-ref_FWT.h : is another simple .h file that contains the declaration of your reference (CPU) function for Fast Wavelet Transform.
5-ref_FWT.c : contains the definition of your CPU model FWT which basically is the C version of the FWT pseudo code that you see above.
6- main.cc: is your interface program

• It gets the input Signal and QMF filter from their respective files.
• It calls CPU FWT routine.
• Sequoia API is used to run the Sequoia code on PS3.
• A common CPU version sorter is used to sort both SEQUOIA and CPU results
• Finally in the main there is a CPU common compare routine that compares the results of CPU and Sequoia program.

7- you may also need to add some additional files for the reason of optimization.

Part 1

• It Is all theory. Like Lab2 part 1.
• WHAT YOU HAVE TO DO?
  • You just have to convert the reference code to inner tasks and a leaf and write some simple mapping files. You don’t need to make it work yet.

1-You have to write your Sequoia code for FWT. Write the appropriate inner and leaf functions in your FWT.sq. You have to just make some minor changes to the original C version and make inner and leaf versions of FWT.
2-Writing the mapping file includes filling up the mapping_ps3.xml file (ignore alignment,granularity, …) and set the constraints in FWT.h.

• We have provided a more complete guide for mapping for you. Most parts of optimization in your implementation are done in mapping file.

3-You also have to give a specific mapping file, for a cluster of 4 PS3 systems with respect to number of memory hierarchy levels (ignore alignment,granularity, …). This is to test your understanding of sequoia concepts and mapping.

• ’ You Also have to think about how to deal

with boundary conditions and overlaps here. ’

For further info about how to write codes refer to :

1. Sequoia Language Reference
2. Sequoia Mapping Reference

Question 1

How did you write your mapping code? Describe the mapping. Please Give a short report on mapping and modeling.

Question 2

‘ ’This is a question about modeling performance and that it’s an important step because it will let you analyze your code later and decide what needs to be optimized and how much potential there is for increased performance.′
What are the parameters and constraints of the system? Please give a variable name for each of these parameters:

• The memory hierarchy,
• Number of processing elements,
• Clock frequency ,
• Peak performance (note that it is dependent to clock frequency)
• Memory capacity
• Memory bandwidth
• and ….
• derive a rough estimate using the variables for the performance you expect to get.
  • Performance Modeling : Discuss the process and memory utilization of your FWT.
  How much is the peak performance of the system and how much your FWT utilizes it?

Discuss the effects of each of these constraints and derive formula for extracting performance regarding the timing result variable T.

Don’t forget that you have input data size and size of the filter as your constraints too.

• You can ignore alignment, this is just to test overall understanding of Sequoia.

By 11/13, I would like you to give me a short report on how you implemented the FWT, what optimizations you performed in mapping files.

Part 2

• WHAT YOU HAVE TO DO

Make your FWT work. Map your code to the PS3 and deal with Cell’s annoying alignment constraints and memory system issues.
Begin by testing our reference CPU functions ref_FWT.c and ref_FWT.h .
This means that you also have to start writing your main.cc to get the input files and call the FWT reference routines for the CPU.
concentrate on optimizing specific 24-tap filter (the number is chosen to reflect the length of filter required for one type of wavelet). For simplicity we will be using floating-point only. The QMF Filter is also provided for you. Once the FWT mapping and source files are written you should write the main.cc program that performs the Fast Wavelet Transform. You have to complete the main.cc in order to let it call the Sequoia using appropriate API. The API documentation is not provided in the Sequoia web page yet. We will give a brief description of common API function calls.

• SqPutData: Those index variables are used to indicate where in the array the input data will be placed. The thing is in 2d arrays you put data line by line in the sequoia part and tell it from which index to put the data and how long is the input data.
• You don’t have to worry about optimization yet, just get things to work here.
• Important: Follow the sample codes closely! This is a pre-alpha compiler and it is very flaky. For example, where you increment a loop induction variable makes a difference and may crash the compiler. “assert(0) at line XXXX” is the only error-reporting mechanism, which could be very frustrating so please do us all a favor and stick to the examples as closely as possible. I’ll try to help as fast as I can, but I don’t remember all the peculiarities at this point.

Also, remember that for the wavelet transform the input length must be a power of 2, and please assume that the CoarsestScale ≥ 3.

Run your application using the wavelet QMF and the input data that will be provided in the appropriate directory on the systems.

Question 3

Please compare your predicted performance and the real gained results. If you have to redefine your previous formula indicate where you have made mistakes and how you found it out. Don’t forget that you have input data size and size of the filter as you constraints too. Provide a table of the predicted and real results and discuss about it.

• By 11/28 please send us your reports containing your opinions on the performance of the

application, including some results. As before make your code available as well.

Part 3

now that you have a wavelet that works on PS3 I want you to optimize your mapping files and report the answer of question 4. This part just focuses on the effects of mapping optimizations.

Question 4

Describe of the effects of the following mapping options on the results.

• SWP(SoftWare Pipelining)
• Unrolling
• Number of ways in SPMD
• Other sorts of optimization that you think are effective here
• Choose the best combination and compare it with the normal mapping performance.

Complete the homework by writing up your results and methods. The report should include the following:

Description of the general FWT filter and an evaluation of its suitability to PS3.

Description of the 24-tap optimized filter including the reasoning behind your algorithm choice, optimizations you performed, and scheduling results.

Analysis of the wavelet compression application. Describe the application, what problems you encountered, simulation results, and the characteristics of the application (compute-bound/memory-bound, where performance was lost, … ).