1.1 Symmetric Multiprocessing

Symmetric multiprocessing (SMP) uses a single copy of the operating system on all the system’s cores. The operating system has visibility into all system elements and can allocate resources to multiple cores with little or no guidance from the application developer. SMP dynamically allocates resources to specific applications rather than to cores, which leads to greater utilization of available processing power. Key characteristics of SMP include:

• • A collection of homogeneous cores with a common view of system resources such as sharing a coherent memory space and using CPUs that communicate using a large coherent memory space.
• • Applicable for general-purpose applications or applications that may not be entirely known at design time. Applications that may need to suspend because of memory accesses, or may need to migrate or restart on any core, fit into an SMP model as well. Multithreaded applications are SMP friendly.
• • SMP is not as good for specific known tasks like data-intensive applications such as audio, video, or signal processing.

1.2 Asymmetric Multiprocessing

Asymmetric multiprocessing (AMP) can be:

• • homogeneous—each CPU runs the same type and version of the operating system; or
• • heterogeneous—each CPU runs either a different operating system or a different version of the same operating system.

In heterogeneous systems you must either implement a proprietary communications scheme or choose two OSs that share a common API and infrastructure for interprocessor communications. There must be well-defined and implemented methods for accessing shared resources.

In an AMP system an application process will always runs on the same CPU, even when other CPUs run idle. This can lead to one CPU being underutilized or overutilized. In some cases it may be possible to migrate a process dynamically from one CPU to another. There may be side effects of doing this such as requiring checkpointing of state information or a service interruption when the process is halted on one CPU and restarted on another CPU. This is further complicated if the CPUs run different operating systems.

In AMP systems the processor cores communicate using large coherent bus memories, shared local memories, hardware FIFOS, and other direct connections.

AMP is better applied to known data-intensive applications where it is better at maximizing efficiency for every task in the system such as audio and video processing. AMP is not as good as a pool of general computing resources.

The key reason there are AMP multicore devices is because they are the most economical way to deliver multiprocessing to specific tasks. The performance, energy, and area envelope is much better than SMP.

3.1 Multicore Processing Granularity

Granularity can be described as the ratio of computation to communication in a parallel program. There are two types of granularity (as shown in Fig. 12).

Fine-grained parallelism implies partitioning the application into small amounts of work leading to a low computation-to-communication ratio. For example, if we partition a “for” loop into independent parallel computions by unrolling the loop, this would be an example of fine-grained parallelism. One of the downsides to fine-grained parallelism is that there may be many synchronization points—for example, the compiler will insert synchronization points after each loop iteration, which may cause additional overhead. Moreover, many loop iterations would have to be parallelized to get decent speedup, but there the developer has more control over load-balancing the application.

Coarse-grained parallelism is where there is a high computation-to-communication ratio. For example, if we partition an application into several high-level tasks that then get allocated to different cores, this would be an example of coarse-grained parallelism. The advantage of this is that there is more parallel code running at any point in time and fewer synchronizations are required. However, load-balancing may not be ideal as the higher level tasks are usually not all equivalent as far as execution time is concerned.

Let’s take one more example. Let’s say we want to multiply each element of an array A by a vector X (Fig. 13). Let’s think about how to decompose this problem into the right level of granularity. The code for something like this would look like:

for (i = 0, N-1)
 for (j = 0, N-1)
   y[i] = A[i,j] * x[j];

From this algorithm we can see that each output element of y depends on one row of A and all of x. All tasks are of the same size in terms of number of operations.

How can we break this into tasks? Course grained with a smaller number of tasks or fine grained with a larger number of tasks. Fig. 14 shows an example of each.

4.1 Load Imbalance

Load imbalance is the time that processors in the system are idle due to (Fig. 21):

• • Insufficient parallelism (during that phase).
• • Unequal size tasks.

Unequal size tasks can include things like tree-structured computations and other fundamentally unstructured problems. The algorithm needs to balance load where possible and the developer should profile the application on the multicore processor to look for load-balancing issues. Resources can sit idle when load-balancing issues are present.

4.2 Data Parallelism

Data parallelism is a parallelism approach in which multiple units process data concurrently. Performance improvement depends on many cores being able to work on the data at the same time. When the algorithm is sequential in nature, difficulties arise. For example, cryptoprotocols, such as 3DES (triple data encryption standard) and AES (advanced encryption standard) are sequential in nature and therefore difficult to parallelize. Matrix operations are easier to parallelize because data are interlinked to a lesser degree (we have an example of this coming up).

In general, it is not possible to automate data parallelism in hardware or with a compiler because a reliable, robust algorithm is difficult to assemble to perform this in an automated way. The developer has to own part of this process.

Data parallelism represents any kind of parallelism that grows with the data set size. In this model the more data you give to the algorithm, the more tasks you can have and operations on data may be the same or different. But the key to this approach is its scalability.

Fig. 22 shows the scalable nature of data parallelism.

In the example given in Fig. 23 an image is decomposed into sections or “chunks” and partitioned to multiple cores to process in parallel. The “image in” and “image out” management tasks are usually performed by one of the cores (an upcoming case study will go into this in more detail).

4.3 Task Parallelism

Task parallelism distributes different applications, processes, or threads to different units. This can be done either manually or with the help of the operating system. The challenge with task parallelism is how to divide the application into multiple threads. For systems with many small units, such as a computer game, this can be straightforward. However, when there is only one heavy and well-integrated task the partitioning process can be more difficult and often faces the same problems associated with data parallelism.

Fig. 24 is an example of task parallelism. Instead of partitioning data to different cores the same data are processed by each core (task), but each task is doing something different on the data.

Task parallelism is about functional decomposition. The goal is to assign tasks to distinct functions in the program. This can only scale to a constant factor. Each functional task, however, can also be data parallel. Fig. 25 shows this. Each of these functions (atmospheric, ocean, data fusion, surface, wind) can be allocated to a dedicated core, but only the scalability is constant.

6.1 Select the Right “Core” for Your Multicore

Do you need a latency-oriented core or a throughput-oriented core? Do you need hardware acceleration or not? Is a heterogeneous architecture needed or a homogeneous one? It makes a big difference from a performance perspective. I put this in this section as well because it makes software programming more efficient without having to resort to fancy tips and tricks to get decent performance. But it does require benchmarking and analysis of the core and software development tools such as the compiler and the operating system.

6.2 Improve Serial Performance Before Migrating to Multicore (Especially Instruction-Level Parallelism)

Early in the development process, before looking at optimizations specific to multicore, it’s necessary to spend time improving the serial (single-core) application performance. Sequential execution must first be efficient before moving to parallelism to achieve higher performance. Early sequential optimization is much easier and less time consuming and less likely to introduce bugs.

Many performance improvements obtained in serial implementation will close the gap on the parallelism required to achieve your goals when moving to multicore. It’s much easier to focus on parallel execution alone during this migration, instead of having to worry about both sequential and parallel optimization at the same time.

Just be careful not to introduce serial optimizations that degrade or limit parallelism (such as unnecessary data dependencies) or overexploiting details of the single-core hardware architecture (such as cache capacity).

Focus on instruction-level parallelism (ILP). The compiler can help. The main goal of a compiler is to maintain the functionality of the application and support special functionality provided by the target and the application such as pragmas, instrinsics, and other capability like OpenMP, which we will discuss further. For example, the “restrict” keyword (C99 standard of the C programming language) is used in pointer declarations, basically telling the compiler that for the lifetime of the pointer only it or a value derived from it (such as pointer + 1) can be used to access an object it points to. This limits the effects of memory disambiguation or pointer aliasing, which enables more aggressive optimizations. An example of this is given below. In this example stores may alias loads. This forces operations to be executed sequentially:

void VectorAddition(int *a, int *b, int *c)
{
 for (int i = 0; i < 100; i ++)
   a[i] = b[i] + c[i];
}

In this example the “restrict” keyword allows independent loads and stores. Operations can now be performed in parallel:

void VectorAddition(int restrict a, int *b, int *c)
{
 for (int i = 0; i < 100; i ++)
   a[i] = b[i] + c[i];
}

The “restrict” keyword can enable more aggressive optimizations such as software pipelining. Software pipelining is a powerful loop optimization usually performed by the compiler back end. It consists of scheduling instructions across several iterations of a loop. This optimization (Fig. 28) enables instruction-level parallelism, reduces pipeline stalls, and fills delay slots. Loop iterations are scheduled so that an iteration starts before the previous iteration has completed. This approach can be combined with loop unrolling (see below) to achieve significant efficiency improvements.

Loop transformations also enable ILP. Loops are typically the hotspots of many applications. Loop transformations are used to organize the sequence of computations and memory accesses to better fit the processor internal structure and enable ILP.

One example of a loop transformation to enable ILP is called loop unrolling. This transformation can decrease the number of memory accesses and improve ILP. It unrolls the outer loop inside the inner loop and increases the number of independent operations inside the loop body.

Below is an example of a doubly nested loop:

for (i = 0; i < N; i +++)
{
 for (j = 0; j < N; j ++)
 {
   a[i][j] = b[j][i];
 }
}

Here is the same loop with the loop unrolled, enabling more ILP:

for (i = 0; i < N; i +++)
{
 for (j = 0; j < N; j ++)
 {
   a[i][j] = b[j][i];
   a[i + 1][j] = b[j][i + 1];
 }
}

This approach improves the spatial locality of b and increases the size of loop body and therefore the available ILP. Loop unrolling also enables more aggressive optimizations such as vectorizations (SIMD) by allowing the compiler to use these special instructions to improve performance even more (as shown in Fig. 29 where the “move.4w” instructions are essentially SIMD instructions operating on four words of data in parallel).

As with all optimizations you need to use the right ones for the application. Take the example of video versus audio algorithms. For example, audio applications are based on a continuous feed of data samples. There are lots of long loops to process. This is a good application structure to use software pipelining, which works well in this situation.

Video applications, on the other hand, are designed to break up video frames into smaller blocks (like the example earlier, we called this minimal coded units, MCUs). This type of structure uses small loop counts and many blocks of processing. Software pipelining in this case is not as efficient due to the long prologs required for pipelining. There is too much overhead for each loop. In this case it’s best to use loop unrolling instead, which works better and more efficiently for these smaller loops.

There are many other examples of sequential optimization. The key message is to make sure you apply these first before worrying about other parallel optimizations.

6.3 Achieve Proper Load Balancing (SMP Linux) and Scheduling

Multicore-aware operating systems like Linux have infrastructure to support multicore performance at the system level such as SMP schedulers, different forms of synchronization, load-balancers for interrupts, affinity-scheduling techniques and CPU isolation. If used properly, overall system performance can be optimized. However, they all have some inherent overhead so they must be used properly.

Linux is a multitasking kernel that allows more than one process to exist at any given time. The Linux process scheduler manages which process runs at any given time. The basic responsibilities are:

• • Share the cores equally among all currently running processes.
• • Select the appropriate process to run next (if required), using scheduling and process priorities.
• • Rebalance processes between multiple cores in SMP systems if necessary.

Multicore applications are generally categorized to be either CPU bound or I/O bound. CPU-bound applications spend a lot of time using the CPU to do computations (like server applications). I/O-bound applications spend a lot of time waiting for relatively slow I/O operations to complete (e.g., like a smartphone waiting for user input, network accesses, etc.). There is obviously a trade-off here. If we let our task run for longer periods of time, it can accomplish more work but responsiveness (to I/O) suffers. If the time period for the task gets shorter, our system can react faster to I/O events. But now more time is spent running the scheduling algorithm between task switches. This leads to more overhead and efficiency suffers.

6.4 Improve Data Locality

Although this was discussed earlier, there are some additional comments to be made concerning software optimizations related to data locality. This is a key focus area for multicore optimization. In many applications this requires some careful analysis of the application. For example, let’s consider a networking application that is using the Linux operating system.

In the Linux operating system all network-related queues and buffers use a common data structure called sk_buff. This is a large data structure that holds all the control information needed for a network packet. sk_buff structure elements are organized as a doubly linked list. This allows efficient movement of sk_buff elements from the beginning/end of a list to the beginning/end of another list.

The standard sk_buff has information spread over three or more cache lines. Data-plane applications require only one cache line’s worth of information.

We can take advantage of this by creating a new structure that packs/aligns to a single cache line. If we are smart and make this part of the packet buffer headroom, then we don’t have to worry about cache misses and flushes each time we access the large sk_buff structure. Instead we use a small portion of this that fits neatly into the cache, improving data locality and efficiency. This is shown in Fig. 30.

6.5 Reduce or Eliminate False Sharing

False sharing occurs when two software threads manipulate data that are on the same cache line. As we discussed earlier the memory system of a multicore processor must ensure cache coherency in SMP systems. Any modifications made to shared cache must be flagged to the memory system so each processor is aware the cache has been modified. The affected cache line is “invalidated” when one thread has changed data on that line of cache. When this happens the second thread must wait for the cache line to be reloaded from memory (Fig. 31).

The code below shows this condition. In this example sum_temp1 may need to continually reread “a” from main memory (instead of from cache) even though inc_b’s modification of “b” should be irrelevant.

In this situation if the extra prefetched words are not needed and another processor in this cache-coherent, shared memory system must immediately change these words, this extra transfer has a negative impact on system performance and energy consumption:

struct data
{
  volatile int a;
  volatile int b;
};

data f;

int sum_temp1()
{
  int s = 0;
  for (int i = 0; i < 1000; i ++)
 s += f.a;
  return s;
}

void inc_b()
{
  for (int i = 0; i < 1000; i ++)
 ++f.b;
}

One solution to this condition is to pad the data in the data structure so that the elements causing false-sharing performance degradation will be allocated to different cache lines:

6.6 Use Affinity Scheduling When Necessary

In some applications it might make sense to force a thread to continue executing on a particular core instead of letting the operating system make the decision whether or not to move the thread to another core. This is referred to as “processor affinity.” Operating systems like Linux have APIs to allow a developer to control this, allowing them the ability to map certain threads to cores in a multicore processor (Fig. 32).

On many processor architectures any migration of threads across cache, memory, or processor boundaries can be expensive (flushing the cache, etc.). The developer can use APIs to set the affinities for certain threads to take advantage of shared caches, interrupt handing, and to match computation with data (locality). A snippet of code that shows how to do this is:

#define _GNU_SOURCE
#include < sched.h >
long
sched_setaffinity(pid_t pid, unsigned int len,
     unsigned long *user_mask_ptr);
long
sched_getaffinity(pid_t pid, unsigned int len,
     unsigned long *user_mask_ptr);

In this code snippet the first system call will set the affinity of a process. The second system call retrieves the affinity of a process.

The PID argument is the process ID of the process you want to set or retrieve. The second argument is the length of the affinity bitmask. The third argument is a pointer to the bitmask. Masks can be used to set the affinity of the cores of interest.

If you set the affinity to a single CPU this will exclude other threads from using that CPU. This also takes that processor out of the pool of resources that the OS can allocate. Be careful every time you are manually controlling affinity scheduling. There may be side effects that are not obvious. Design the affinity-scheduling scheme carefully to ensure efficiency.

6.7 Apply the Proper Lock Granularity and Frequency

There are two basic laws of concurrent execution:

1. 1. The program should not malfunction.
2. 2. Concurrent execution should not be slower than serial execution.

We use locks as a mutual exclusion mechanism to prevent multiple threads getting simultaneous access to shared data or code sections. These locks are usually implemented using semaphores or mutexes, which are essentially expensive API calls into the operating system.

Locks can be fine grained or coarse grained. Too many locks increases the amount of time spent in the operating system and increases the risk of deadlock. Coarse-grained locking reduces the chance of deadlock, but can cause additional performance degradations due to locking large areas of the application (mainly system latency).

Avoiding heavy use of locks and semaphores due to performance penalties. Here are some guidelines:

• • Organize global data structures into buckets and use a separate lock for each bucket.
• • Design the system to allow threads to compute private copies of a value and then synchronize only to produce the global result. This will require less locking.
• • Avoid spinning on shared variables waiting for events.
• • Use atomic memory read/writes to replace locks if the architecture supports this.
• • Avoiding atomic sections when possible (an atomic section is a set of consecutive statements that can only be run by one thread at a time).
• • Place locks only around commonly used fields and not entire structures if this is possible.
• • Compute all possible precalculations and postcalculations outside the critical section, as this will minimize the time spent in a critical section.
• • Make sure that locks are taken in the same order to prevent deadlock situations.
• • Use mechanisms that are designed to reduce overhead in the operating system. For example, in POSIX-based systems use the trylock() function that allows the program to continue execution to handle an unsuccessful lock. In Linux use the “futex” (fast user space mutex) to do resource checks in user space instead of the kernel (see Fig. 33).

  
  

6.8 Remove Sync Barriers Where Possible

A synchronization barrier causes a thread to wait until the other threads have reached the barrier and is used to ensure that variables needed at a given execution point are ready to be used. It differs from a lock for this very reason (Fig. 33).

Barriers can have the same performance problem as locks if not used properly. Oversynchronizing can negatively impact performance. This is the reason barriers should only be used to ensure that data dependencies are respected and/or where the execution frequency is the lowest.

A barrier can be used to replace creating and destroying threads multiple times when dealing with a sequence of tasks (i.e., replacing join and create threads). Hence when used in this way certain performance improvements can be realized.

6.9 Minimize Communication Latencies

When possible limit communication in multicore systems. Even extra computing is often more efficient than communication in many cases. For example, one approach to minimize communication latencies is to distribute data by giving each CPU has its own local data set that it can work on. This is called per-cpu data and is a technique used in the Linux kernel for several critical subsystems. For example, the kernel slab allocator uses per-cpu data for fast CPU local memory allocation. The disadvantage is higher memory overhead and increased complexity dealing with CPU hotplug.

In general, the communication time can be estimated using the following:

$T_{com}\left(n\right)=\alpha +{\beta }^{\ast }n$

where n is the size of the message, α is the startup time due to the latency, and β is the time for sending one data unit limited by the available bandwidth.

Here are a few other tips and tricks to reduce communication latency:

• • Gather small messages into larger ones when possible to increase the effective communications bandwidth (reduce β, reduce α, increase n).
• • Sending noncontiguous data is usually less efficient than sending contiguous data (increases α, decreases n).
• • Do not use messages that are too large. Some communication protocols change when messages get too large (increases α, increases n, increases β).
• • The layout of processes/threads on cores may affect performance due to communication network latency and the routing strategy (increases α).
• • Use asynchronous communication techniques to overlap communication and computation. Asynchronous communication (nonblocking) primitives do not require the sender and receiver to “rendezvous” (decrease α).
• • Avoid memory copies for large messages by using zero-copy protocols (decrease β).

6.10 Use Thread Pools

When using a peer or master/worker design, like the one we discussed earlier, users should not create new threads on the fly. This causes overhead. Instead have them stopped when they are not being used. Creating and freeing processes and threads is expensive. The penalty caused by the associated overhead may be larger than the benefit of running the work in parallel.

In this approach a number of threads are allocated to a thread pool. N threads are created to perform a number of operations M, where N ≪ M. When a threads completes the task it’s working on, it will then request the next task from the thread pool (usually organized into a queue) until all the tasks have been completed. The thread can then terminate (or sleep) until new tasks become available. Fig. 34 is a conceptual diagram of this.

A thread pool is implemented as a data structure as:

typedef struct _threadpool{
 int num_threads;    //number of active threads
 int qsize;    //queue size
 pthread_t *threads;    //pointer to threads
 work_t* qhead;    //queue head pointer
 work_t* qtail;    //queue tail pointer
 pthread_mutex_t qlock;   //lock on the queue list
 pthread_cond_t q_not_empty; //nonempty and empty condition vairiables
 pthread_cond_t q_empty;
 int shutdown;
 int dont_accept;
} thread_pool;

The associated C code can be implemented to control access to the thread pool’s data structure. This is not shown here, but there are plenty of examples you can find that show reference implementations.

6.11 Manage Thread Count

As discussed earlier, parallel execution always incurs some overhead resulting from functions such as task startup time, intertask synchronization, data communications, hardware bookkeeping (e.g., memory consistency), software overhead (libraries, tools, runtime system, etc.), and task termination time.

As a general rule, small tasks (fine grain) are usually inefficient due to the overhead to manage many small tasks. Large tasks could lead to load imbalance. In many applications there is a trade-off between having enough tasks to keep all cores busy and having enough computation in each task to amortize the overhead.

The optimal thread count can also be determined by estimating the average blocking time of the threads running on each core:

$\text{T}\text{h}\text{r}\text{e}\text{a}\text{d}\text{c}\text{o}\text{u}\text{n}\text{t}=\text{n}\text{u}\text{m}\text{b}\text{e}\text{r}\text{o}\text{f}\text{c}\text{o}\text{r}\text{e}\text{s}/\left(1-\text{p}\text{e}\text{r}\text{e}\text{n}\text{t}\text{a}\text{g}\text{e}\text{a}\text{v}\text{e}\text{r}\text{a}\text{g}\text{e}\text{b}\text{l}\text{o}\text{c}\text{k}\text{i}\text{n}\text{g}\text{t}\text{i}\text{m}\text{e}\text{o}\text{f}\text{t}\text{h}\text{r}\text{e}\text{a}\text{d}\text{s}\right)$

6.12 Stay Out of the Kernel If at All Possible

We gain a lot of support from operating systems, but when optimizing for performance it’s sometimes better to not go in and out of the operating system often, as this incurs overhead. There are many tips and tricks for doing this, so study the manual for the operating system and learn about the techniques available to optimize performance. For example, Linux supports SMP multicore using mechanisms like “futex” (fast user space mutex).

A futex is comprised of two components:

• • A kernelspace wait queue.
• • An integer in userspace.

In multicore applications the multiple processes or threads operate on the integer in userspace and only use expensive system calls when there is a need to request operations on the wait queue (Fig. 35). This would occur if there was a need to wake up waiting processes, or put the current process in the wait queue. Futex operations do not use system calls except when the lock is contended. However, since most operations do not require arbitration between processes this will not happen in most cases (Fig. 36).

6.13 Use Concurrency Abstractions (Pthreads, OpenMP, etc.)

For larger multicore applications, attempting to implement the entire application using threads is going to be difficult and time consuming. An alternative is to program atop a concurrency platform. Concurrency platforms are abstraction layers of software that coordinate, schedule, and manage multicore resources. Using concurrency platforms, such as OpenMP, thread-building libraries, and OpenCL, can not only speed time to market but also help with system-level performance. It may seem counterintuitive to use abstraction layers to increase performance. But these concurrency platforms provide frameworks that prevent the developer from making mistakes that could lead to performance problems.

Writing code for multicore can be tedious and time consuming. Here is an example showing the sequential code for a dot product:

#define SIZE 1000
Main() {
 double a[SIZE], b[SIZE];
 // Compute a and b
 double sum = 0.0;
 for(int i = 0, i < SIZE; i ++)
   sum += a[i] * b[i];
 // use sum….
}

Now let’s implement this same dot product using pthreads for a four-core multicore processor. Here is the code:

#include < iostream >
#include < pthread.h >
#define THREADS 4
#define SIZE 1000
using namespace std;
double a[SIZE], b[SIZE], sum;
pthread_mutex mutex_sum;
void *dotprod(void *arg) {
 int my_id = (int)arg;
 int my_first = my_id * SIZE/THREADS;
 int my_last = (my_id + 1) * SIZE/THREADS;
 double partial_sum = 0;
 for(int i = my_first; i < my_last && i < SIZE; i ++)
   partial_sum += a[i] * b[i];
 pthread_nmutex_lock(&mutex_sum);
 sum += partial_sum;
pthread_mutex_unlock(&mutex_sum);
pthread_exit((void*)0);
}
int main(int argc, char *argv[]) {
// compute a and b…
pthread_attr_t attr;
pthread_t threads[THREADS];
pthread_mutex_init(&mutex_sum, NULL);
pthread_attr_init(&attr);
pthread_attr_setdetachstate(&attr, PTHREAD_CREATE_JOINABLE);
sum = 0;
for(int i = 0; i < THREADS; i ++)
pthread_create(&threads[i], &attr, dotprod, (void*)i);
 pthread_attr_destroy(&attr);
 int status;
 for(int i = 0, i < THREADS; i ++)
   pthread_join(threads[i], (void**)&status);
 // use sum….
 pthread_mutex_destroy(&mutex_sum);
 pthread_exit(NULL);
}

As you can see, this implementation, although probably much faster on a multicore processor, is rather tedious and difficult to implement correctly. This do-it-yourself approach can definitely work, but there are abstractions that can be used to make this process easier. That is what this section is all about.

Multicore programming can be made easier using concurrency abstractions. These include but are not limited to:

• • Language extensions
• • Frameworks
• • Libraries

There exists a wide variety of frameworks, language extensions, and libraries. Many of these are built upon pthreads technology. Pthreads is the API of POSIX-compliant operating systems, like Linux, used in many multicore applications.

Let’s take a look at some of the different approaches to provide levels of multicore programming abstraction.

8.1 Image-Processing Example

Let’s explore this process in more detail by looking at an example. We will use an image-processing example shown in Fig. 42. We will use an edge detection pipeline for this example.

A basic sequential control structure for the edge detection example is:

Let’s now work through the steps we discussed earlier to see how we can apply this approach to this example.

We will start with Step 2: Sequential analysis. Fig. 43 shows that the three processing steps are unbalanced when it comes to total processing load. The “Smooth” function dominates the processing, followed by the “Detect” function and then the “Correct” function. By looking at the code above, we can also come to the conclusion that each function is embarrassingly data parallel. There is constant work per pixel in this algorithm, but also a very different amount of work per function (as can be seen in Fig. 43). This is also the time to make sure that you are only using thread-safe C libraries in this function, as we will be migrating this to multicore software using threads.

Let’s move on to Step 3: Exploration. As mentioned previously this is the step where we explore different parallelization strategies such as:

• • Quick analysis/design, coding, and verification iterations
• • Favor simplicity over performance
• • Verify each iteration
• • Focus on dependencies and decomposition granularity

We decompose to expose parallelism. Keep in mind these rules:

• • Prioritize hotspots
• • Honor dependencies
• • Favor data decomposition

Remember we may also need to “recompose” (we sometimes call this agglomeration) considering:

• • Workload granularity and balance
• • Platform and memory characteristics

During exploration, don’t overthink it. Focus on the largest, least interdependent chunks of work to keep N cores active simultaneously. Use strong analysis and visualization tools to help you (there are several of them we will talk about later).

Let’s move on to Step 4: Optimization and tuning. We will follow these important rules of thumb during the optimization and tuning phase:

• • Follow good software-engineering practices
• • Code incrementally
• • Code in order of impact
• • Preserve scalability
• • Don’t change two things at once

In this step you must also verify changes often. Remember, parallelization introduces new sources of error. Reuse sequential tests for functional verification even though the results may not be exact due to computation order differences. Check for common parallelization errors such as data races and deadlock. Perform stress-testing where you change both the data as well as the scheduling at the same time. Perform performance bottleneck evaluation.

8.2 Data Parallel; First Attempt

The strategy for attempt 1 is to partition the application into N threads one per core. Each thread handles width/N columns. The different image regions are interleaved. We create a thread for each slice as shown in line 10 of the code below and then we join them back together in line 13. How this is partitioned is shown in Fig. 44.

1 void *edge_detect(char unsigned *out_pixels, char unsigned *in_pixels,
2 int nrows, int ncols) {
3 ed_arg_t arg[NUM_THREADS];
4 pthread_t thread[NUM_THREADS];
5 int status, nslices, col0, i;
6 nslices = NUM_THREADS;
7 for (i = 0; i < nslices; ++i) {
8 col0 = i;
9 pack_arg(&arg[i], out_pixels, in_pixels, col0, nslices, nrows, ncols);
10 pthread_create(&thread[i], NULL, edge_detect_thread, &arg[i]);
 11 }
 12 for (i = 0; i < nslices; ++i) {
 13 pthread_join(thread[i], (void *)&status);
14 }
15 return NULL;
16 }

How does this work? Well, not so well. I have introduced a functional error into the code. Diagnosis (Fig. 45) shows that I have introduced a RAW data dependency. Basically there is a race condition in which Smooth₀ can read the image data before being written by the Correct function. You can see this error in Fig. 46.

8.3 Data Parallel; Second Attempt

Let’s try this again. The fix to this specific problem is to finish each function before starting the next to prevent the race condition. What we will do is “join” the threads after each function before starting the subsequent function to alleviate this problem. The code below shows this. We create threads for the Correct, Smooth, and Detect functions in lines 3, 8, and 13, respectively. We add “join” instructions at lines 5, 10, and 15. We can see how this works graphically in Fig. 47.

1 for (i = 0; i < nslices; ++i) {
2 pack_arg(&arg[i], out_pixels, in_pixels, i, nslices, nrows, ncols);
3 pthread_create(&thread[i], NULL, correct, &arg[i]);
4 }
5 for (i = 0; i < nslices; ++i) pthread_join(thread[i], (void *)&status);
6 for (i = 0; i < nslices; ++i) {
7 pack_arg(&arg[i], in_pixels, out_pixels, i, nslices, nrows, ncols);
8 pthread_create(&thread[i], NULL, smooth, &arg[i]);
9 }
10 for (i = 0; i < nslices; ++i) pthread_join(thread[i], (void *)&status);
11 for (i = 0; i < nslices; ++i) {
12 pack_arg(&arg[i], out_pixels, in_pixels, i, nslices, nrows, ncols);
13 pthread_create(&thread[i], NULL, detect, &arg[i]);
14 }
15 for (i = 0; i < nslices; ++i) pthread_join(thread[i], (void *)&status);

This is now functionally correct. One thing to note. Interleaving columns probably is not good for data locality, but this was easy to get working. So let’s take the “make it work right, then make it work fast” approach for the moment.

8.4 Task Parallel; Third Attempt

The next strategy is to try to partition functions into a simple task pipeline. We can address the load-balancing concern mentioned earlier by delaying the Smooth and Detect functions until enough pixels are ready. Fig. 48 shows this pipelining approach.

The code for this is shown below. We create our queues in lines 3 and 5. Three threads are created for each function in the algorithm in line 7. We fill our queues in lines 10 and 11, and then join the threads back together in line 13.

1 stage_f stage[3] = { correct, smooth, sobel };
2 queue_t *queue[4];
3 queue[0] = queue_create(capacity);
4 for (i = 0; i < 3; ++i) {
5 queue[i + 1] = queue_create(capacity);
6 pack_arg(&arg[i], queue[i + 1], queue[i], nrows, ncols);
7 pthread_create(&thread[i], NULL, stage[i], &arg[i]);

8 }
9 while (*in_pixels) {
10 queue_add(queue[0], *in_pixels ++);
11 } queue_add(queue[0], NULL);
12 for (i = 0; i < 3; ++i) {
13 pthread_join(thread[i], &status);
14 }

The results are improved throughput but not latency. The throughput is limited by the longest stage (1/85% = 1.12x). This approach would be difficult to scale with a number of cores. The latency is still the same but, like a pipeline, throughput improves. Remember that the stages are very unbalanced, so performance is not very good (Fig. 49). We could consider doing data parallelism within the longest stage to better balance the stages. A comparison of sequential and pipelined schedules is shown in Fig. 50.

8.5 Exploration Results

So far we have some interesting exploration results. We should go with the data decomposition approach. We should match the number of threads to the number of cores, since the threads are compute intensive with few data dependencies to block them. There are still some tuning opportunities that we can take advantage of. We have seen some interleaving concerns in one of our approaches and experienced some delay required for the pipelining design.

8.6 Tuning

We eventually want to identify and optimize performance issues. These could include thread stalls, excessive synchronization, and cache thrashing.

This is where we iterate and experiment. Vary the number of threads and number of cores. Look for ways to minimize locking. Try to separate threads from tasks in different ways to see the impact.

Analysis shows the results of this recent approach made performance worse than the sequential code (Fig. 51)! Diagnosis shows false sharing between caches and significant performance degradation.

8.7 Data Parallel; Fourth Attempt

Let’s try a new strategy. Let’s partition the application into contiguous slices of rows. This should help with data locality and potentially eliminate the false-sharing problem as well. The code for this is shown below. We will refactor the code to process slices of rows for each thread for each function. We create the row slices for the Correct function in lines 1–4, then create the threads in line 5. We do a similar thing for the Smooth and Detect functions before joining them all back together again in line 26.

1 for (i = 0; i < nslices; ++i) {
2 row0 = i * srows;
3 row1 = (row0 + srows < nrows)? row0 + srows : nrows;
4 pack_arg(&arg[i], out_pixels, in_pixels, row0, row1, nrows, ncols);
5 pthread_create(&thread[i], NULL, correct_rows_thread, &arg[i]);
6 }
7 for (i = 0; i < nslices; ++i) {
8 pthread_join(thread[i], (void *)&status);
9 }
10 for (i = 0; i < nslices; ++i) {
11 row0 = i * srows;
12 row1 = (row0 + srows < nrows)? row0 + srows : nrows;
13 pack_arg(&arg[i], in_pixels, out_pixels, row0, row1, nrows, ncols);
14 pthread_create(&thread[i], NULL, smooth_rows_thread, &arg[i]);
15 }
16 for (i = 0; i < nslices; ++i) {
17 pthread_join(thread[i], (void *)&status);
18 }
19 for (i = 0; i < nslices; ++i) {
20 row0 = i * srows;
21 row1 = (row0 + srows < nrows)? row0 + srows : nrows;
22 pack_arg(&arg[i], out_pixels, in_pixels, row0, row1, nrows, ncols);
23 pthread_create(&thread[i], NULL, detect_rows_thread, &arg[i]);
24 }
25 for (i = 0; i < nslices; ++i) {
26 pthread_join(thread[i], (void *)&status);
27 }

8.8 Data Parallel; Fourth Attempt Results

The results of this iteration are better. We have good localization of data and there is good scalability as well. Data locality is important in multicore application. Traditional data layout optimization and loop transformation techniques apply to multicore since they

• • minimize cache misses
• • maximize cache line usage
• • minimize the number of cores that touch a data item

Use the guidelines discussed earlier to achieve the best data locality for the application and significant performance results will be achieved. Use profiling and cache measurement tools to help you.

8.9 Data Parallel; Fifth Attempt

We are now at a point where we can continue to make modifications to the application to improve cache performance. We can split rows into slices matching the L1 cache width of the device (an example of this is blocking where the image can be decomposed into the appropriate block sizes as shown in Fig. 52). We can process rows by slices for better data locality. In the end, additional data layout improvements are possible. Some of these could have been sequential optimizations, so make sure you look for those opportunities first. When migrating to multicore it makes it easier having already incorporated key optimizations into the sequential application.

8.10 Data Parallel; Work Queues

As an additional tuning strategy we can try using work queues (Fig. 53). In this approach we attempt to separate the number of tasks from the number of threads. This enables finer grained tasks without extra thread overhead. Locking and condition variables that can cause extra complexity are hidden in work queue abstractions.

When we use this approach the results get better as slices get smaller (Fig. 54). The key is to tune empirically. In this example we sacrificed some data locality—the work items are interleaved, but empirically this is minor. The results are improved load balancing, some loss of data locality, easy-to-tune thread, and work item granularity.

1 #define SLICES_PER_THREAD 5
2 nslices = NUM_THREADS * SLICES_PER_THREAD;
3 srows = nrows / nslices; if (nrows % nslices) ++srows;
4 crew = work_queue_create("Work Crew", nslices, NUM_THREADS);
5 for (i = 0; i < nslices; ++i) {
6 r0 = i * srows;
7 r1 = (r0 + srows < nrows)? r0 + srows : nrows;
8 pack_arg(&arg[i], out_pixels, in_pixels, r0, r1, nrows, ncols);
9 work_queue_add_item(crew, edge_detect_rows, &arg[i]);
10 } work_queue_empty(&crew);

8.11 Going too Far?

Can we do even more? Probably. We can use task parallel learning to compose three functions into one. We can do some more complex refactoring like lagging row processing to honor dependencies (Fig. 55). This could lead to a threefold reduction in thread creates and joins. This is possible with only minor duplicated computations at the region edge. This modest performance improvement comes with increased coding complexity. See the code below to implement lag processing in this application.

This code is certainly more efficient, but it’s noticeably more complex. Is it necessary? Maybe or maybe not. Is the additional performance worth the complexity? This is a decision that must be made at some point. “Excessive optimization” can be harmful if the performance is not needed. Be careful with “premature optimization” and “excessive optimization.”

1 void *edge_detect_rows(pixel_t out_pixels[], pixel_t in_pixels[],
2 int row0, int row1, int nrows, int ncols) {
3 int rc, rs, rd, rs_edge, rd_edge;
4 int nlines, scols, c0, c1, i;
5 pixel_t *corrected_pixels, *smoothed_pixels;
6 corrected_pixels = MEM_MALLOC(pixel_t, SMOOTH_SIDE * ncols);
7 smoothed_pixels = MEM_MALLOC(pixel_t, DETECT_SIDE * ncols);
8 // determine number of line splits
9 nlines = ncols / CACHE_LINESIZE;
10 scols = ncols / nlines;
11 if (ncols % nlines) ++scols;
12 for (i = 0; i < nlines; ++i) {
13 c0 = i * scols;
14 c1 = (c0 + scols < ncols)? c0 + scols : ncols;
15 log_debug1("row %d:%d col %d:%d
", row0, row1, c0, c1);
16 for (rc = row0; rc < row1 + SMOOTH_EDGE + DETECT_EDGE; ++rc) {
17  if (rc < nrows) {
18  correct_row(corrected_pixels, in_pixels, rc % SMOOTH_SIDE, rc,
20   c0, c1, ncols);
21  }
22  rs = rc - SMOOTH_EDGE;
23  if (0 <= rs && rs < nrows) {
24  rs_edge = (rs < SMOOTH_EDGE || nrows - SMOOTH_EDGE <= rs) ? 1 : 0;
25  smooth_row(smoothed_pixels, corrected_pixels, rs % DETECT_SIDE,
26   rs_edge, rs % SMOOTH_SIDE, SMOOTH_SIDE, c0, c1, ncols);
27  }
28  rd = rs - DETECT_EDGE;
29  if (0 <= rd && rd < nrows) {
30 rd_edge = ((rd < DETECT_EDGE) ? -1 : 0) +
31     ((nrows - DETECT_EDGE <= rd) ? 1 : 0);
32  detect_row(out_pixels, smoothed_pixels, rd, rd_edge,
33   rd % DETECT_SIDE, DETECT_SIDE, c0, c1, ncols);
34 } } }
35 MEM_FREE(corrected_pixels);
36 MEM_FREE(smoothed_pixels);
37 return NULL;
38 }