Parallel programming on Playstation 3 (Cell architecture) by example: Puzzle solving

• Download puzzle_solving - 38.85 KB
• Download tests - 563.84 KB

Introduction

The purpose of this article is to offer programmers a birds eye view of the programming model for the new Playstation 3 console. To do this, I structured the article in two parts: the first part is a presentation of the hardware architecture, the programming model and where to find resources, its APIs and how to use them. The second part shows an example application: we will try to solve a puzzle using as many of the programming features offered as possible.

Part 1: The Cell

Historical Context

As the need for processing power grows, hardware designers find it increassing difficult to satisfy the demand.

The first obstacle is the so called "frequency wall" that basically sais that we can only go so far by increasing the processor frequency because we get diminishing returns for deeper pipelines. A related obstacle is the heat dissipation ("power wall") that, as power consumption grows becomes even more difficult.

Another obstacle is the "Memory Wall". Memory works at a very small speed compared with the CPU; the several layers of memory (hard drive, RAM, cache L3, cache L2, cache L1) do their best to hide this latency, but todays systems are often limited by memory speed.
Possible solutions to increase the performance are: increasing efficiency and increasing concurrency.

The alliance formed in 200 by Sony, IBM and Toshiba aimed for both. The processing architecture they created, named Cell Broadband Engine, is now used both in consumer products (Playstation 3) that require great processing power (like 3D games) and on servers.

Architecture overview

The architecture is an eterogenous multicore architecture: we have a Power Processing Element (PPE) for control tasks and 8 Synergetic Processing Elements (SPE) for data intensive processing.

The Cell architecture is, from Flynn taxonomy point of view, as being MIMD (Multiple Instructions operating on Multiple Data). That is, we can see the Cell as 9 separate processors on a single die, one of the being the master and offering work for the others and the others doing the actual work.

The Cell PPE is a 64 bit RISC PowerPC processor working at 3.2GHz, 2-way hardware multi threaded and with separate L1 caches for instructions and data and a unified L2 cache.

The Cell SPEs are 8 per chip and offer Integer and floating Point operations and a local store of 256 KB. The interesting choice of the designers was to replace the on chip cache with this local store memory (normal memory, not associative like caches). Each SPE offers 4 floating point units and integer units si that at each moment 4 mathematical operations can take place. As you can see, the performance does not come only by increasing the concurrency at the number of cores, but also in each core. To control these units we use a SIMD (Single Instruction, Multiple Data) flow; this means we can process a vector of 4 32 bit elements at the same time, but we can apply only one (and the same) operation to all elements in the vector. Alternatively, we can use halfword data types for the same operations.

Parallel programming on MIMD machines is becoming even more popular these days, so much of the information in this article is not only interesting but also useful, because you can better understand how to write code that uses todays multicore processors better. Remember that currently many people have dual core or even quad core processors and its a shame not to harness that power.

Programming Tools and APIs

To program for the Cell, we must use the Cell SDK found in the IBM Cell Broadband Engine Resource Center (http://www.ibm.com/developerworks/power/cell/). You cand find there a lot of useful information on both the hardware and the programming model used.

The quickest way to get a functional environment for Cell programming is to download a Cell virtual Machine, for example from this page.

Actual programming takes place in Linux using this SDK and optionally The Eclipse IDE for which there are a couple of plugins that offer integration with the compiler for Cell. The Cell SDK includes a Simulator which allows one to program for Cell without actual access to Cell hardware.

The Programming Model

From the programmers perspective, the language we use is C++, with special extensions.
Lets analyse the programming model for Cell.

The usable libraries for the SPEs and the PPE are different (this is normal, considering that the hardware resources are different); this means that some functions work only in SPE code, others in PPE code; you have to check the manual for this. Usually, the header file taht contains the functions gives a hint ( for example, spu_mfcio.h is used for for spu memory IO access)

Spe Threads

A general Cell program will have a piece of code like this in the PPE code; this code is used to load the executable images on the SPEs and start them, offering the parameters they expect.

void *spe_thread( void *voidarg ) 
{

  thread_args_t *arg = (thread_args_t *)voidarg;

  unsigned int runflags = 0;
  unsigned int entry = SPE_DEFAULT_ENTRY;

  spe_context_run( arg->spe_context, &entry, runflags, arg->argp, arg->envp, NULL );
  pthread_exit( NULL );
}

void StartSpu(int i, int* originalPieceAddr, int** data)
{
    sprintf(buffer,"%d %d", piece_height, (int)originalPieceAddr);
    printf("Started SPU with %d %d %d and buffer %s", 
            originalPieceAddr[0], 
            originalPieceAddr[1],
            originalPieceAddr[2], buffer);
    spe_contexts[i] = spe_context_create( SPE_EVENTS_ENABLE, NULL ); 

    events[i].spe = spe_contexts[i];
    events[i].events = SPE_EVENT_OUT_INTR_MBOX;
    events[i].data.u32 = i; 
    spe_event_handler_register(handler, &events[i] );
    spe_program_load( spe_contexts[i], &spu );
    thread_args[i].spe_context = spe_contexts[i];
    thread_args[i].argp = buffer;
    thread_args[i].envp = buffer;

    pthread_create( &threads[i], NULL, &spe_thread, &thread_args[i] );

}

Programmers with Linux programming experience using the pthread library will find the spe thread creation process quite familiar.

Mailboxes

Naturally, we want to support communication between the SPEs and the PPE. This is done usually by using a feature called Mailboxes. The mailbox is used to send short messages (32 bits) from the SPE to the PPE or form a SPE to the PPE and is generally used for synchronization between the two. We can use the mailboxes in two ways:
1. by blocking. The receiver waits until it receives a message, doing nothing in that time
2. by polling. The receiver periodically checks for a message, then does some work and repeats this process until it receives a message

Obviously, the option that has a better performance is the second option because it does not lead to a "busy waiting" approach (the PPU waits for a message and cannot do anything in that time). To initialize the mailbox a small amount of code is required, like this:

events[i].events = SPE_EVENT_OUT_INTR_MBOX; // setting the type of events we use
spe_event_handler_register(handler, &events[i] ); //register the handler for the specified events

In the mailbox the PPE will receive messages from any SPE so we want to know the exact SPE that sent the message. We do this by association a number to each SPE, number that we can obtain along with the received data:

events[i].data.u32 = i;

Waiting for a message in the PPE is done like this:

spe_event_wait(handler, events_generated, NUM_THREADS, -1);
//printf("Got event! from spe no %d:", events_generated[0].data.u32);
spe_out_intr_mbox_read (events_generated[0].spe,(unsigned int*) &data, 1, SPE_MBOX_ANY_BLOCKING);

And sending a message from the PPE is done like this:

spe_in_mbox_write( events_generated[0].spe, value_p, 1, SPE_MBOX_ANY_BLOCKING);

Mailboxes allow only basic syncronisation techniques. Primitives like barriers , semaphores and fences are still required and used on Cell.

DMA Access

As I said earlier , Mailboxes are used for synchronization between the PPE and the SPEs, that is so that the PPE knows what each SPE is doing at a certain time. But the need to send data to the SPEs arises. The SPEs are good at tasks involving intense data processing so sending 32 bits at a time is out of the question. To send data from a PPE to the SPE we use DMA access. In normal , x86 C++ programming, you don't have to use the DMA explicitly, but using it like this offers better control, flexibility and thus performance.

int tag = 30;  
int tag_mask = 1<<tag;
mfc_get((volatile void*)original_piece, (uint64_t)originalPieceAddrAsInt, piece_height*piece_height*sizeof(int), tag, 0, 0);    
mfc_write_tag_mask(tag_mask);
mfc_read_tag_status_any();

The actual transfer is done using the mfc_get function. This function starts the transfer of piece_height*piece_height*sizeof(int) bytes, starting from the originalPieceAddrAsInt address in the PPE memory, to the SPE the code runs on; the data is written starting at original_piece.
Tagging is an optional feature of DMA transfers and allows selective waiting for DAM transfers to complete. Generally, when we want to wait for a DMA to complete we use a read_status function, like this:

mfc_read_tag_status_all();

DMA actually means a special hardware exists that takes the burden of IO transfers form the CPU, leaving it free to do what it knows best: processing data. This is a hardware optimization technique known as specialization, which was also used by the Cell designers when the decided to have SPUs and a PPE with different capabilities.

When we want to wait for a particular DMA, we apply a tag to it when we start it and when we wait for it, we apply a tag mask:

mfc_write_tag_mask(tag_mask);
mfc_read_tag_status_any();

The tag mask is a integer in which the bit in the position corresponding to the tag of the desired transfer(s) is 1. This corresponds to a bit shift:

int tag_mask = 1<<tag;

Tags make an optimization technique called "double buffering" possible. Double buffering essentially means starting a DMA transfer before you actually need the data; you request the data for the next step, and process data from the current step. By the time you finished processing the data , the next step data has already arrived. This is used to hide the memory latency that is mentioned at the beginning of the article. Double buffering is well-known for its use in graphical systems where, by keeping the next frame to display in memory you can reduce flickering.

SIMD Processing

The Cell SPU libs offer functions that map to intrinsec ASM instruction of the Cell; the most interesting of these are the SIMD instruction; they allow operations on more than one variable at a time, specifically a maximum of four 32 bit variables(integers or floating point). These operations require use of a new data type called vector that allows grouping of these variables. The main limitation of these vectors it that they must be arranged in memory at 128 bit boundaries. This is done for statically allocated data by using the aligned attribute:

int temp[MAX_LEN] __attribute__ ((aligned(128)));

and for dynamic data by using the memalign function:

piece_pos = (int*)memalign(128, piece_height*piece_height*sizeof(int));

Vector types are: vector int, vector float, vector char, etc and operations include addition, subtraction, division, etc.
We can add the 4 elements found in two vectors A and B and put the result in another vector C: C[0]=A[0]+B[0] ...C[3]=A[3]+B[3]. using the spu_add function which takes A and B as parameters and returns C.
More complicated SIMD functions allow other operation like comparing 4 32 bit numbers concurrently:

// vi - vector int
cmp = spu_sub( *((vi*)puzzle_piece), *((vi*)original_piece));
zero = spu_orx(cmp);
if (*( (int*)(&zero) ) != 0) return 0; 

Part 2: Puzzle Solving

The goal of this exercise is to solve a puzzle. We start with two images: the original image and a modified image which might be the original image split into pieces and the pieces shuffled and rotated ( 0, 90, 180, 270 degrees )s o that a new image results. Knowing the puzzle piece size (in pixels) we want to reconstruct the original image from the two images. Output will be the reconstructed image (so that we can see that the result is OK) and a text file showing where each original piece is in the puzzle image. We want to make the most efficient use of the Cell processor. Also, the program must work correctly with images that have multiple identical pieces.

My solution include use of:
- concurrency through SPEs
- DMA access
- Mailboxes
- Double Buffering

I decided to use a simple format for the images: the text bsed ppm (http://netpbm.sourceforge.net/doc/ppm.html) format; this format basically uses r g b pixel format stored as ASCII text and separated by simple delimiters (like spaces). This makes the task of actually understanding the image format easier and allows us to focus on the processing that is to be done. It is not the most performance-oriented format though. We want to be able to process images of normal size (at list of 1280*1024 resolution) using pieces of size from 2*2 to 64*64 and 65500 colors (so taht a pixel fits a single integer).

The basic protocol of communication between the SPEs and the PPE goes like this:

1. the PPE starts the SPE threads

2. The PPE remembers the current original_piece that is sent to each SPE and the current puzzle_piece sent to each SPE. Each SPE will get a original_piece and then he will receive puzzle_pieces until he identifies a puzzle piece as being identical to his original piece. The request for original_pieces and puzzle_pieces will use mailboxes and the actual data will be sent through DMA. To request another puzzle_piece the SPU send back a 0. To announce that his puzzle_piece and his original_piece match, the SPE returns 1,2,3,4 according to the rotation tht he identified.When there are no more puzzle pieces for comparison, the PPE respons to the puzzle_piece request by refusing it(send 0). If there are more puzzle_pieces it send a pointer to the region of memory in which the puzzle piece resides.
The main loop for the SPE looks like this:

    while ( NULL != (original = RequestNewOriginalPiece(length)) )
    { 
        FindPuzzlePieceForOriginalPiece(piece_height);
    }

The problem that appears it that if we want to use a single DMA transfer to transfer a piece in one go, the piece must be located in a continuous area in memory. If we read the image as it is in the file, the puzzle piece will be spread out; thus, we need to read each puzzle piece in an array by changing each pixels coordinates:

    for(j=0; j<height; j++)
        for(i=0; i< width; i++)
        {
            p_no_y = j / piece_height;
            piece_offset = (j - p_no_y*piece_height) * piece_height;

            p_no_x = i / piece_height;
            piece_offset += i - p_no_x*piece_height;  // pixel offset in piece

            piece_no = p_no_y* (width/piece_height) +p_no_x; // get number of piece from piece coordinates

            fscanf(f_original, "%d", &r);
            fscanf(f_original, "%d", &g);
            fscanf(f_original, "%d", &b);
            original[piece_no][piece_offset] = (r<<16) + (g<<8) + b; // cram pixel data in a single int
        }

The SPE double buffering is another interesting code area:

        turn++;
        if (turn%2 == 1) 
        {
            // wait for tranfer1
            // !!!value =  transfer1.addr;
            value =  (float*)transfer1.addr;
            // !!!printf("Waiting for transfer 1 at addr %d.\n", value);
            //printf("Waiting for transfer 1 at addr %d.\n", (int)value);
            if ( transfer1.addr != 0)
            {
                //printf("Transfer1 not 0.\n");
                //printf("Checking tranfer status for tag = %d",transfer1.tag);
                mfc_write_tag_mask(1<<transfer1.tag);
                mfc_read_tag_status_any();
                // use tranfer1
                //printf("Tranfer 1 data (%d %d %d) length %d\n", transfer1.buffer[0],transfer1.buffer[1], transfer1.buffer[2], length);
                memcpy(input, transfer1.buffer, length*4); 
                // start transfer 2:
                // -request a new backup DMA tranfer address
                //printf("Sending request for transfer2.\n");
                spu_write_out_intr_mbox(match_result);
                addr = spu_read_in_mbox();
                //printf("Got addr=%d", addr);
                transfer2.addr = addr;
                // -initialize actual tranfer
                transfer2.tag = transfer1.tag + 1;
                if (transfer2.tag>30) 
                { 
                    transfer2.tag -= 30;
                    //printf("Decremented tag.\n");
                } 
                tag_mask = 1<<transfer2.tag;
                if (addr != 0)
                { 
                        mfc_get((volatile void*)transfer2.buffer, (uint64_t)addr, length * 4, transfer2.tag, 0, 0);
                }
                else
                {
                        //printf("Don't wait\n");
                }
            }

This code leaves a lot of place for optimisation. The "turn" varible allows for selecting the actual buffer to use, but because the double buffering structs transfer1 and transfer2 are not in an array, we cannot try to see it triple or 4-time buffering further improves performance. Changing this code is a good exercise for the reader.

We take advantage of the SIMD capabilities when we test for equality the two pieces:

int test_equality(int* puzzle_piece, int* original_piece, int piece_height)
{
    vi zero,cmp;
    int i = 0; 

    for(i=0; i<piece_height*piece_height/4; i++)
    {
        cmp = spu_sub( *((vi*)puzzle_piece), *((vi*)original_piece));
        zero = spu_orx(cmp);
        if (*( (int*)(&zero) ) != 0) return 0;
        puzzle_piece += 4;
        original_piece += 4;
    }
    return 1;
}

SIMD operations can be used also for the rotation process. Their use however generates very complex code and is extremely difficult to understand so its place is not here. If you have the time and interest, you might find it a good exercise for your mind to find the answer.

An interesting situation that need to be treated adequately is this: Lets assume that the iamge contains multiple pieces that are the same. Then the two places from the original image that are the same must be filled with the two pieces from the puzzle image, and NOT with the same puzzle piece! If the program were sequential, we could stop this process simply by not sending a puzzle piece that is already fitted in the image for checking if it fits another position. But, considering we have 8 concurrent instruction streams (and thus 8 pieces are being processed at the same time ) this cannot be done. The simplest way to handle this case is by checking (when the result from the spe comes as a positive) if the position of the puzzle piece was not already used. (Attention: Checking this before sending to the spu is not enough!). Another, and more interesting approach would be to always have different pieces in processing ar the same time, but this approach is more complicated to code.

References

1. The SDK and the Programming Standards sectiond in the Docs page of the IBM Cell Resource Center

• Cell Broadband Engine Programmer's Guide (updated)

• Cell Broadband Engine Programming Tutorial (updated)

• Cell Broadband Engine Programming Handbook

• SIMD Math Library Specification for Cell Broadband Engine Architecture

• C/C++ Language Extensions for Cell Broadband Engine Architecture
  

2. The wonderfull course on the Structure of Computer Systems held at the Politehnica University of Bucharest, faculty of Computer Science

License

The code is licensed under a proprietary license. Any use of this code is allowed only after my explicit permission.

You must Sign In to use this message board.

FAQ  Noise Tolerance Very HighHighMediumLowVery Low  Search Messages    Layout Expand All MessagesThread ViewNo Javascript (slow)No Javascript Preview    Per page 102550

Msgs 1 to 10 of 10 (Total in Forum: 10) (Refresh) FirstPrevNext

Cannot get it to finish? Snejs 11:30 17 Oct '08   Hi! I'm trying to run this example on a PS3 using SDK3.0. It compiles fine and starts to run. But it never finishes. I've even created smaller pictures to test. It seems that it starts each spu, and thats it. Any ideas why? BRs Snejs Sign In·View Thread·PermaLink Re: Cannot get it to finish? Dragos Dumitru Sbarlea 11:38 17 Oct '08   This program was tested on SDK 2.1. I do not have a machine with SDK 3.0, but I suspect that there might be changes in the API between these two versions that break the program. Sign In·View Thread·PermaLink Any advice for testing the program icestatue 11:42 27 Aug '08   I have been reading up as much as I can about this enviroment, however, there is a huge amount of manuals to read still. Do you have any advice on how to load the applications developed into the simulator (MySim if memory serves me right) I am not quit sure what programs get loaded where for the simulator to work. Any advice would be welcome. nothing Sign In·View Thread·PermaLink Re: Any advice for testing the program EliteXR 4:08 3 Sep '08   Hi, I'm sure this link will help you: http://ww2.cs.fsu.edu/~west/cell/index.php?tutorial=start[^] Please be aware that the sites uses the old SPE library libspe, so don't rely on it when learning how to manage the SPEs using this library, although there are many sites that explain the recent library libspe2. Regards Game Programming is Fun! Sign In·View Thread·PermaLink Correction [modified] EliteXR 20:47 14 Jul '08   Hi, I think you have a mistake in the text. In the "Architecture overview" part, the forth paragraph particularly. You wrote: "this means we can process a vector of 4 elements at the same time". Well, that doesn't necessary means that a vector can only handle four elements at a time, the register size on these inner cores and specially on the SPE is 128 bits, which means it can handle up to 16 Byte at time. When you said it can process four elements at a time, you meant the integer type exclusively - which is 32bit data type. Say if I choose a different type for my vector, say char type, wouldn't I be able to make a vector which consists of 16 elements Hmm, another mistake is located in the "DMA Access", in the paragraph below the code. you wrote: "This function starts the transfer of piece_height*piece_height*sizeof(int) bits", you should change it into bytes, this is completely wrong since the smallest unit for data transfer in here is byte, not bit I found it very interesting article especially the "Architecture" part, you got to work on the typos here as mentioned before. Thank you for this great article Regards, Game Programming is Fun! modified on Tuesday, July 15, 2008 2:24 AM Sign In·View Thread·PermaLink Re: Correction Dragos Dumitru Sbarlea 22:45 14 Jul '08   "this means we can process a vector of 4 elements at the same time" As far as I used to know, vector operations were done only on 32 bit data types. On further research i discovered (in the depths of the documentation specified that it is legal to use half-word data types, but i did not find evidence that smaller types can be used. I will mke the appropriate change. "This function starts the transfer of piece_height*piece_height*sizeof(int) bits" You are completely right. This kind of mistake is very confusing for beginners programmers and I am truly sorry for having done it The sizeof operator in C++ returns the size of a type in multiples of the char data type size, as you have observed. Thank you for your competent and constructive comment. Sign In·View Thread·PermaLink Re: Correction EliteXR 22:47 14 Jul '08   You're so welcome my friend Regards, Game Programming is Fun! Sign In·View Thread·PermaLink Performance? kfoust 3:41 26 Feb '08   I'm extremely interested in the CBE and have started looking at how this can help speed up my operations research (OR) data models. I'd love to see a performance comparison of this versus a standard C++ implementation of the same problem. Provided, of course, this was work was done with the actual CBE and not a simulated environment. Have you been doing comparisons to see real-world benefits? Any information you have on this would be very valuable to me. Thanks, and nice article. There are no stupid questions, but there are a lot of inquisitive idiots. Sign In·View Thread·PermaLink Nice article psouza4micronet 4:34 19 Feb '08   It's a nice article with a lot of solid data in it. You do need to go back and clean up all of the many typos though, for readability. Sign In·View Thread·PermaLink Re: Nice article Dragos Dumitru Sbarlea 5:04 19 Feb '08   Tanx for your opinion. I will follow your advice asap Sign In·View Thread·PermaLink 3.00/5 (2 votes)

Last Visit: Thursday, January 8, 2009 3:26 PM     Last Update:Thursday, January 8, 2009 3:26 PM