Efficient Multicore Programming with OpenMP Solution

OpenMP China MCP 1

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Getting Started with OpenMP on KeyStone & Keystone II 2

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Getting Started with OpenMP on KeyStone & Keystone II 3

Motivation: TI Multicore Perspective Medical Imaging Mission Critical Test and Automation Image3 Garmin G1000 EFIS by olaborda lm_verigy_hp93000_1990_intro http://t3.gstatic.com/images?q=tbn:jbGzS1ja8jWVFM:http://www.fintexs.com.my/userfiles/image/Vision-System-Automation/large/Product-inspection-to-detect-defects.jpg atm-y.jpg High Performance Compute Emerging Emerging Broadband innovatorslead http://t2.gstatic.com/images?q=tbn:1wK-CDYlP85h4M:http://faculty.kfupm.edu.sa/ES/akwahab/RML_Se14.gif http://t1.gstatic.com/images?q=tbn:9YOl5oLz8gYhkM:http://topnews.net.nz/images/Supercomputing.jpg http://t3.gstatic.com/images?q=tbn:38f_76EdVdfV4M:http://www.telecoms.com/files/2009/07/wirelessearth2-300x247.jpg Multichannel & Next Generation Video H.265, SVC, etc. blade http://t0.gstatic.com/images?q=tbn:HMyIVIH3L8Y7qM:http://prafimo.com.au/wp-content/uploads/2010/07/financial_modeling-300x225-150x150.jpg 4

Motivation: Migrate SW from Single to Multicore Earlier with Single Core New, faster processor would give desired performance boost Faster execution speed was a result of better hardware Minimal effort from software developers Porting sequential code was straight forward Now with Multicore Boost in performance not only function of hardware Need to master software techniques that leverage inherent parallelism of multicore device Every semiconductor vendor has own software solution Many are new to multicore software development and have existing sequential code to port 5

Motivation: The Need An efficient way to program multicore that is: Easy to use and quick to implement Scalable Sequential-coder friendly Portable and widely adopted 6

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Getting Started with OpenMP on KeyStone & Keystone II 7

The OpenMP Solution What is OpenMP? An API for writing multi-threaded applications API includes compiler directives and library routines C/C++ and Fortran support in general. C/C++ support on TI devices. Standardizes last 20 years of Shared-Memory Programming (SMP) practice 8

The OpenMP Solution: How does OpenMP address the needs? Easy to use and quick to implement Minimal modification to source code Compiler figures out details Scalable Minimal or no code changes to add cores to implementation Sequential-coder friendly Allows incremental parallelization v/s all-or-nothing approach Allows unified code base for sequential and parallel versions Portable and widely adopted Ideal for shared-memory parallel (SMP) architectures Open-source and community-driven effort Architecture Review Board includes:TI, Cray, Intel, NVidia, AMD, IBM, HP, Microsoft and others 9

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Getting Started with OpenMP on KeyStone & Keystone II 10

Features: OpenMP Solution Stack EndUser Application Directives, Compiler Environment variables OpenMP library Runtime library OS/system 11

Features: OpenMP API consists of Compiler Directives and Clauses: Specifies instructions to execute in parallel and its distribution across cores Example: #pragma omp construct [clause [clause] .. ] Library Routines: Execution Environment Routines Configure and monitor threads, processors, and parallel environment Example: int omp_set_num_threads (int) Lock Routines Synchronization with OpenMP locks Example: void omp_set_lock (omp_lock_t *) Timing Routines Support portable wall clock timer Example: double omp_get_wtime(void) Environment Variables: Alter execution features of applications like default number of threads, loop iteration scheduling, etc. Example: OMP_NUM_THREADS 12

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Create Teams of Threads Share Work among Threads Manage Data-Scoping Synchronize Threads and Variables Getting Started with OpenMP on KeyStone & Keystone II 13

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Create Teams of Threads Share Work among Threads Manage Data-Scoping Synchronize Threads and Variables Getting Started with OpenMP on KeyStone & Keystone II 14

Implementation: Use OpenMP to Create Teams of Threads Fork-Join Model Execute code in a parallel region Implemented by using compiler directive #pragma omp parallel Nesting parallel directives is possible, allowing multilevel parallelism Master Thread Sequential Region ID:0 Parallel Region Starts Fork Threads execute simultaneously Team of Threads (created automatically) ID:3 ID:1 ID:0 ID:2 Parallel Region Ends Wait till all threads terminate Join Master Thread Sequential Region 15

Implementation: Parallel Construct Include Header API definitions #include <ti/omp/omp.h> void main() { omp_set_num_threads(4); #pragma omp parallel { int tid = omp_get_thread_num(); printf ("Hello World from thread = %d\n", tid); Library Function Set # of threads (typically # of cores) Compiler Directive Fork team of threads Library Function Get thread id Implicit Barrier } } 16

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Create Teams of Threads Share Work among Threads Manage Data-Scoping Synchronize Threads and Variables Getting Started with OpenMP on KeyStone & Keystone II 17

Implementation: Use OpenMP to Share Work among Threads By default each thread redundantly executes all code in // region Programmer can insert work-sharing constructs to express how computation should be distributed Example: Distribute for loop Applicable only to loops where iterations are independent, i.e. changing order of execution won t matter #pragma omp for Example: Distribute multiple tasks #pragma omp section 18

Implementation: Work-sharing Constructs Sequential Code for(i=0;i<N;i++) { a[i] = a[i] + b[i]; } #pragma omp parallel { int id, i, Nthrds, istart, iend; id = omp_get_thread_num(); Nthrds = omp_get_num_threads(); istart = id * N / Nthrds; iend = (id+1) * N / Nthrds; for(i=istart;i<iend;i++) { a[i] = a[i] + b[i]; } } Only with Parallel Construct Parallel and Work- sharing Constructs #pragma omp parallel #pragma omp for for(i=0;i<N;i++) { a[i] = a[i] + b[i]; } 19 Source: Reference #3

Implementation: Work-sharing Constructs #pragma omp parallel #pragma omp sections { #pragma omp section x_calculation(); #pragma omp section y_calculation(); } #pragma omp section z_calculation(); By default, there is a barrier at the end of the omp sections Use the nowait clause to turn off the barrier. 20 Source: Reference #5

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Create Teams of Threads Share Work among Threads Manage Data-Scoping Synchronize Threads and Variables Getting Started with OpenMP on KeyStone & Keystone II 21

Implementation: Use OpenMP to Manage Data-scoping using Clauses Control how variables should be treated in a parallel region Clauses private clause Each thread has a private copy of this variable and a unique value throughout the parallel construct Variable declared inside parallel region is automatically private Stored in thread stack; default size set by compiler but can override shared clause Same copy of this variable is seen by all threads Variable declared outside parallel region is automatically shared (part of MSMC or DDR3) defaultclause Override default scope assigned to any variable Set to noneto explicitly specify scope of all variables used inside // Programmer s responsibility to declare which variables are shared / private Some variables like iteration counts, the compiler automatically enforces 22

Implementation: Data-Scoping Clauses #pragma omp parallel for default (none) private( i, j, sum ) shared (A, B, C) if (flag) { for (i = 0, i < 10; i++) { sum = 0; for ( j = 0; j < 20; j++ ) sum += B[ i ][ j ] * C [ j ]; A[ i ] = sum; } } 23

Agenda Motivation: The Need The OpenMP Solution OpenMP Features OpenMP Implementation Create Teams of Threads Share Work among Threads Manage Data-Scoping Synchronize Threads and Variables Getting Started with OpenMP on KeyStone & Keystone II 24

Implementation: Use OpenMP to Synchronize Threads Synchronization at the end of work-sharing or // construct is automatic. Synchronizing subset of threads has to be manually handled. Some Synchronization Directives: #pragma omp critical <name> Only one thread may enter at a time. Applies to block of code If critical sections are unnamed, threads will not enter any of them. #pragma omp atomic Hardware provides atomic operation for expression Applies to line of code (expression like X+=5) Less overhead but less portability and limited to specific operations #pragma omp barrier Each thread waits until all threads arrive #pragma omp flush[optional list] User can creates sequence point for consistent view of memory Implicit barriers automatically ensure cache coherency 25

Implementation: Synchronization Constructs int sum = 0, i; int A [100] = populate(); #pragma omp for shared (sum, A) { for (i = 0, i < 100; i++) { #pragma omp atomic sum += A [ i ]; } } 26

Implementation: Reduction Construct int sum = 0, i; int A [100] = populate(); #pragma omp for shared (A) reduction (+:sum) { for (i = 0, i < 100; i++) { sum += A [ i ]; } } Reduction creates private copy of shared variable for each thread At end of parallel loop, private copies of variable are reduced back into original shared variable and operator ( + ) is applied 27

Agenda Motivation: The Need The Solution: OpenMP OpenMP Features OpenMP Implementation Getting Started with OpenMP on KeyStone & Keystone II 28

OpenMP on KeyStone: Solution Stack Depends on SYS/BIOS. Each core runs the RTOS. OpenMP master and worker threads execute inside dedicated SYS/BIOS tasks. IPC is used for communication and synchronization. OpenMP run-time state and user data is allocated in shared memory. 29

OpenMP on KeyStone: Availability TI s OpenMP package OMP is installed as part of the MCSDK installation w/ OpenMP programming layer and runtime, and CodeGen 7.4.x compiler. MCSDK v2.1.2.6 is the latest version available, and includes OMP v1.1.3.2 Download MCSDK at http://software- dl.ti.com/sdoemb/sdoemb_public_sw/bios_mcsdk/latest/index_FDS. html Once MCSDK is installed, install update patch for OMP v1.02.00 from http://software- dl.ti.com/sdoemb/sdoemb_public_sw/omp/1_02_00_05/index_FDS.h tml 30

OpenMP on KeyStone: Recent Updates Important to update to latest OMP version which includes: Support for TI s C6657 device, and nested parallelism feature Significant performance boost from previous versions: Inter-core synchronization achieved through Multicore Navigator instead of hardware semaphores, and other optimizations BIOS/IPC related memory for each core moved to MSMC, making L2 entirely available to the developer TIP: Assign OpenMP variable heap & .data memory to MSMC/DDR, and not L2, to ensure variable sharing across cores Refer to OMP release notes and user guide for more details on improvements, bug fixes, and configuration tips related to this release 31

OpenMP on KeyStone II On 66AK2H, OpenMP is available on the ARMs using gcc and the corresponding runtime, libgomp. OpenMP on the DSPs is available via the following programming models: OpenMP Dispatch With OpenCL. A TI-specific extension to the OpenCL which allows OpenCL kernels to dispatch OpenMP regions. OpenMP Accelerator Model. A subset of the OpenMP 4.0 specification that enables execution on heterogeneous devices. 32

OpenMP Dispatch With OpenCL on DSP Depends on TI OpenCL extension OpenCL kernel act as a wrapper that invokes C functions containing OpenMP regions Three components The host program The OpenCL kernel The OpenMP region 33

OpenMP Accelerator Model on DSP OpenMP Accelerator Model is the subset of OpenMP 4.0 specification Host is a Quad Core ARM Cortex-A15 cluster running SMP Linux The target accelerator is a single-cluster consisting of 8 C66x DSP cores. The OpenMP Accelerator model host runtime implementations uses the TI OpenCL Runtime as a back- end. 34

OpenMP on KeyStone: Spawning Threads Use of an event queue for each core for task assignments Scheduler keeps track of the number of threads per core to distribute threads evenly on the cores. Event Queue 0 pop push Create_Task Core0 Create_Thread Event Queue 1 pop push Create_Task Core1 Scheduler Event Queue 2 pop Create_Task Core2 push Event Queue N pop Create_Task CoreN push 35

OpenMP on KeyStone: CCS Demo We will see how to: Access example OpenMP projects from CCS v5.1 Include OpenMP header file #include <ti/omp/omp.h> Specify number of cores in project configuration .cfg OpenMP.setNumProcessors(4); Provide --omp compiler option available as a check box in project settings on CCSv5.1 Build C6000 Compiler Advanced Options Advanced Optimizations Enable Support for OpenMP 3.0 36

References 1. OpenMP on C6000 wiki article http://processors.wiki.ti.com/index.php/OpenMP_on_C6000 2. MCSDK User Guide http://processors.wiki.ti.com/index.php/BIOS_MCSDK_2.0_User_Guide 3. OpenMP Runtime for SYS/BIOS User s Guide Included in OMP/docs folder once you install OMP package 4. OpenMP Specification, http://openmp.org/wp/openmp-specifications/ 5. Using OpenMP, B. Chapman, G. Jost, R. Van Der Pas http://www.amazon.com/Using-OpenMP-Programming-Engineering- Computation/dp/0262533022/ 6. Introduction to OpenMP http://community.topcoder.com/tc?module=Static&d1=features&d2=091106 7. MCSDK-HPC 3.0 Getting Started http://processors.wiki.ti.com/index.php/MCSDK_HPC_3.x_Getting_Started_Guide 37