Algorithms and Parallel Computing

6.1 INTRODUCTION

There is a software gap [49] between hardware potential and the performance that can be attained using today’s software tools. There are now concurrency platforms that support multithreading, such as Cilk++ [50] and Open Multi-Processing (OpenMP) [51] and standard libraries like POSIX threads (Pthreads) [38–40, 52, 53] and WinAPI threads [40]. Using these tools, the program developer is able to control the number of threads and the workload assigned to each thread. The program developer can also control synchronization of the different threads to ensure proper program execution. Using such techniques, the programmer is able to generate a parallel code—that is, a code that contains several threads. However, this code might not automatically result in a concurrent code—that is, a code that runs simultaneously on several cores or processors. Concurrency is controlled ultimately by the operating system [54]. The application developers cannot rely on the software to explore algorithm speedup. Rather, the developer must use special directives to control the progress of tasks even in the presence of operating system uncertainties.

The above tools rely on the application developer or the programmer being able to identify parallelism and to ensure proper program sequencing. This might be easy to do for the simplest cases. For other cases, the programmer needs other tools to investigate the alternative ways to explore possible parallelism. The purpose of this book is to ...