{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# M2.P1. OpenMP\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction to OpenMP\n", "\n", "**OpenMP (Open Multi-Processing)** is an API that supports parallel programming in shared-memory environments. It simplifies the development of parallel applications by providing directives, library routines, and environment variables. \n", "\n", "### Key Goals of OpenMP\n", "- Simplify parallel programming.\n", "- Enable efficient use of multicore processors.\n", "- Allow incremental parallelization of code.\n", "\n", "### Applicability in Modern HPC\n", "OpenMP is used in modern high-performance computing environments such as weather forecasting, scientific simulations, and data analysis. The key advantage is its ease of use with existing codebases in C, C++, and Fortran.\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Introduction to Parallel Programming with OpenMP\n", "\n", "In this practice, we will explore the use of **OpenMP** (Open Multi-Processing), a widely-used API for parallel programming in C, C++, and Fortran. OpenMP provides a simple and flexible interface for developing parallel applications that can take advantage of multi-core and multi-threaded processors, which are common in modern computers.\n", "\n", "### Why OpenMP?\n", "\n", "OpenMP enables the parallelization of code, which can significantly speed up computational tasks by distributing the workload across multiple threads. This is particularly useful in tasks that are computationally intensive, such as simulations, data processing, and complex mathematical calculations.\n", "\n", "### Using C Code and GCC Compiler\n", "\n", "For this exercise, we will write and compile C code using the **GCC** (GNU Compiler Collection) compiler, which supports OpenMP directives. GCC is a powerful and versatile compiler that is widely used in the software development community.\n", "\n", "### Running on Any Multithreaded System\n", "\n", "The code we write can be executed on any computer that supports multithreading, including your local PC or cloud environments like Google Colab. If you're using Google Colab or any environment that might not have GCC installed by default, we will provide instructions to check if the GCC compiler is installed and install it if necessary.\n", "\n", "### Checking and Installing GCC Compiler\n", "\n", "Before we begin, we'll ensure that the GCC compiler is installed on your system. If it's not, the script will attempt to install it for you. This step is crucial to ensure that you can compile and run the C code with OpenMP support.\n", "\n", "Let's proceed with checking the GCC compiler installation.\n" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "GCC is already installed.\n" ] } ], "source": [ "import os\n", "import subprocess\n", "import shutil\n", "\n", "# Function to check if gcc is installed\n", "def check_gcc_installed():\n", " return shutil.which(\"gcc\") is not None\n", "\n", "# Function to install gcc if not installed\n", "def install_gcc():\n", " print(\"GCC is not installed. Attempting to install GCC...\")\n", " install_command = \"apt-get update && apt-get install -y gcc\"\n", " install_process = subprocess.run(install_command, shell=True, capture_output=True, text=True)\n", " \n", " if install_process.returncode == 0:\n", " print(\"GCC installation successful.\")\n", " else:\n", " print(\"GCC installation failed. Please install GCC manually.\")\n", " print(\"Error details:\", install_process.stderr)\n", " raise EnvironmentError(\"GCC installation failed.\")\n", "\n", "# Check if GCC is installed\n", "if not check_gcc_installed():\n", " install_gcc()\n", "else:\n", " print(\"GCC is already installed.\")\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "\n", "## Hello World OpenMP\n", "\n", "Let's print the statement \"Hello world!\" using all the threads. Here the variable tid gives your thread id. Our server has only two threads. Threfore, the Hello world! will be printed twice.\n", "\n", "\n", "### Example - Create your first OPenMP multithread program in C and compile it\n", "In this case we will need to compile the C code. We have saved the following openmp code in the file /openmp/omp_hello.c\n", "\n", "```\n", "#include \n", "#include \n", "\n", "int main(int argc, char *argv[]) {\n", "\n", " int nthreads, tid;\n", "\n", " /* Fork a team of threads with each thread having a private tid variable */\n", " #pragma omp parallel private(tid)\n", " {\n", "\n", " /* Obtain and print thread id */\n", " tid = omp_get_thread_num();\n", " printf(\"Hello World! from thread = %d\\n\", tid);\n", "\n", " /* Only master thread does this */\n", " if (tid == 0) \n", " {\n", " nthreads = omp_get_num_threads();\n", " printf(\"Number of threads = %d\\n\", nthreads);\n", " }\n", "\n", " } /* All threads join master thread and terminate */\n", "\n", " }\n", "```\n", "\n", "What we will do is to execute compile the code `gcc -o omp_helloc -fopenmp omp_hello.c`\n", "Note that the environment variable OMP_NUM_THREADS was used to specify number of threads (2).\n", "and we execute the code `./omp_helloc`\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C program written to hello_world_openmp.c.\n" ] } ], "source": [ "import os\n", "\n", "# Define the path for the C program file\n", "c_program_path = \"hello_world_openmp.c\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(c_program_path):\n", " os.remove(c_program_path)\n", "\n", "# Create and write the C program\n", "c_program = \"\"\"\n", "#include \n", "#include \n", "\n", "int main(int argc, char *argv[]) {\n", "\n", " int nthreads, tid;\n", "\n", " /* Fork a team of threads with each thread having a private tid variable */\n", " #pragma omp parallel private(tid)\n", " {\n", "\n", " /* Obtain and print thread id */\n", " tid = omp_get_thread_num();\n", " printf(\"Hello World! from thread = %d\\\\n\", tid);\n", "\n", " /* Only master thread does this */\n", " if (tid == 0) \n", " {\n", " nthreads = omp_get_num_threads();\n", " printf(\"Number of threads = %d\\\\n\", nthreads);\n", " }\n", "\n", " } /* All threads join master thread and terminate */\n", "\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C program to a file\n", "with open(c_program_path, \"w\") as file:\n", " file.write(c_program)\n", "\n", "print(f\"C program written to {c_program_path}.\")\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And now we will compile it and execute it :" ] }, { "cell_type": "code", "execution_count": 4, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compiling the C program...\n", "Compilation successful, executable 'omp_helloc' created.\n", "OMP_NUM_THREADS set to 2.\n", "Running the program...\n", "Output: Hello World! from thread = 0\n", "Number of threads = 2\n", "Hello World! from thread = 1\n", "\n" ] } ], "source": [ "import subprocess\n", "import os\n", "\n", "# Define the name of the C source file and the output executable\n", "c_program_path = \"hello_world_openmp.c\"\n", "executable_name = \"omp_helloc\"\n", "\n", "# Compile the C program using gcc with OpenMP support\n", "compile_command = f\"gcc -o {executable_name} -fopenmp {c_program_path}\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "if os.path.exists(executable_name):\n", " print(f\"Compilation successful, executable '{executable_name}' created.\")\n", " \n", " # Set the number of threads for OpenMP\n", " os.environ[\"OMP_NUM_THREADS\"] = \"2\"\n", " print(\"OMP_NUM_THREADS set to 2.\")\n", " \n", " # Run the compiled executable\n", " run_command = f\"./{executable_name}\"\n", " run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", " \n", " # Print the output and error (if any) after running the executable\n", " print(\"Running the program...\")\n", " if run_process.stdout:\n", " print(\"Output:\", run_process.stdout)\n", " if run_process.stderr:\n", " print(\"Error:\", run_process.stderr)\n", "else:\n", " print(\"Compilation failed.\")\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can execute it on your own in the shell with this :\n", "```\n", "gcc -o omp_helloc -fopenmp omp_hello.c\n", "export OMP_NUM_THREADS=2\n", "./omp_helloc\n", "```" ] }, { "attachments": { "1cc74176-2955-4a1e-9f85-d501faa6dff4.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAHQAAACrCAIAAAA4kC+KAAAM+UlEQVR4nO2dbUxT1xvAz31rScsqdVAnMxHBEbKWsUQtUxyj7CVuNLFKbSLGDRIXySBZFmCVTF6KybIhYXFZEaNB52ZwXcUs6Zx7LSYbmbCNEWEYpxQ++LKyqDB2B/SF/4ej99/RUlH79Ep3fh/07px7z33uz7Nzz7239z7UzMwMIsBAix1ALEPkAkLkAkLkAkLkAkLkAkLkAkLkAsLiv9xu97lz5yLYbmZmpkqlimCDC5FbcgcHB99+++0ItltbW0vkkmEBECIXECIXECIXECIXkHByk5KSTCZT1EJBCJ0+fXrnzp3r16/XarXFxcXHjh0LvN188eLF4eFhvLx69eoTJ05EM7Z7IJxclUoVNbl+v99sNr/22mtxcXFlZWVms/nRRx+1WCwlJSUTExN4naampgMHDkQnnojAhiyVyWR6vX7NmjUIofr6+s7Ozs7OTtA4jh8/brfbW1paNmzYgEsKCws3b978yiuvtLS0vPnmm6B7ByJ0zzWbzSaTacWKFQghjUZTXl4O2oWnp6ebm5s3btwomMWsWrVqx44dbW1tf/zxh8Fg+Oqrrz755JPMzExc6/F4ampqtFrtk08+uWvXLo/HI2z48ccfFxQUaDQag8EQ2C1KSkr6+vpqamqysrLgDkcghNyUlBS1Wo0QqqysNBqNR44cQQgVFBTABTE0NHT9+vUtW7YEVxmNxunp6XPnzh07diw/P3/Tpk1dXV24au/evQqFoq2tbefOnZ9++qndbsflra2t77zzTmFh4YEDB1auXPnqq6+ePXsWV/X29u7Zs2doaOiNN96AOxyBEMOCXC5HCLndbnz2cDgceHxISkoaHR2FCOLixYsIodTU1OCq5ORkqVR66dKl5557jmVZiUTy0EMP4arMzMyqqiqEkEaj+eabb37//XeE0MTERGtra3V19bZt2xBCOTk5ly9fPnz4cHZ2Nt7qn3/+aW9v5zgO4kBmEUKuy+VCCKlUquLiYpvNxvN8XV0daBBhnkBTFMUwzF9//RVctX79emFZoVD4/X6E0Pnz58fHx59++mme54XVvvjiC2HNF154ITpmUUi5PM9brdaysjK9Xq/X651Op81mA+qzmJUrVyKEXC7XkiVLZlVdvXqV5/lly5YFb5WQkBBceOXKFYRQXl5eYKFSqRSWk5OT7z/geRJ6tuB0Ovv7+00mU3Z2tk6n0+l0VqvV6XQCBZGampqQkNDR0fHUU0/Nqjp58iRFUbm5ucFbURQVXKhUKimKGhwclEgkIfdF09G7bppzT6Ojo1artbS0FDstLi6GC0IqlVZUVHR0dHz99deB5X19fa2trQaDYf7dLT09nWGYwBlCVVXVnj17IhnuvAnRcy0Wi1qtttlseMC1Wq06nU4ul6vV6oGBAaA4tm7d2tvbW1paajAY1q5dK5FIfv755+PHj2dkZNTX1+N1GIYZGhq6dOlSWlraXO0sWbKkqKiosrKyqqoqLS3t9OnTJ0+e/PDDD4HCDk8IuQMDA2q1Oi8vz+l0jo6O6nQ6XI5PdEDQNN3U1PTss8+eOHGiubmZ5/m0tLS33nqrqKiIZW8FaTQad+/eXVRUJEytQlJTU5OYmHj06NGrV6+mpqbu378/JycHLvIwUPhMfebMmYaGBlwkk8kaGhpSUlIC13M4HHjCO09qa2ufeeaZCAa6EAk9W6itrc3Pz8/Ly0tJSenu7u7p6RHOZmq1OnjmNDw8LEx9CAKhZws8zzscDpfLZbFYGhsbA6ssFkvw+nV1dXDD8cIltFyMy+UKvnwIeUEBOhwvXMLJ5Xk+uD+SHjp/yJMIQIhcQIhcQG7Nc//888/z589HsN2MjIzExMQINrgQocgLJ3CQYQEQIhcQIhcQIhcQIhcQIhcQIhcQIhcQdmRkROwYYhZyhQYIGRYAIXIBIXIBIXIBIXIBIXIBIXIBIXIBIXIBIXIBIXIB+dfPmch9hvkT8qWBWdySi7UG/kmYi0Ct4RWzgtBZC4hY/jeCR4qiKIqamZkJLAm5CYtuC52ZmfH7/X6/n/TfucASKYqiaVp4KyhM52WxVp/P5/F4xsbGAt+gJcwFx3EKhUIikTAMg0tCKmZxh/V6vdevX3/kkUei9nbhgsbj8bjdbvzOG03Tc3VeGiHk8/m8Xq/f7ydm5wnHcV6v1+v1+nw+9O8TVSA07rlkNLgHPB6PcIoKCY1PYvhfgHBX+Hy+wClAMDRCCJ/QohtYLODz+cLPqW7JJROve+CO3mii9T4JN+ZGM47/GkQuIEQuIEQuIEQuIOHe/Y0I7e3t/f390HsJg0aj2bp1qyi7Bpd74cKFH3/8EXovYZjrS0JRgAwLgBC5gBC5gBC5gBC5gBC5gBC5gBC5gBC5gDwQci0Wi/A1zFgC/PJ3PuBPpMceD0TPjVXE7LlJSUkFBQXC507r6+t/++03h8MRM9/cFE2uXq+f9TVpjUaj0WgKCgrq6uqENDELGnGGBZx6J2SVXC63WCxJSUlRDgkCceQK+VJwngSj0Wg0Gm02Gy6Uy+WgOT+ihjhyhXH2u+++Ez5rarPZhNFAq9WKElhkEXm2MOvc1d3djRdiIzmoOCc0nudlMhlC6PHHHw8sx5/4FyUkCMTpucLn8jUazd69e3Hun9hDHLmHDx8WhtcVK1aYzeaWlhaTyYS7c8wgjlz8QX9hhEW3swbu378/yokZQRHthMbzfGNjY2VlZWDKH7lcbjKZysrKxIoqsog8WxgeHrZarS+//LLVahVmDjqdTq/XixtYRHggbtzwPO90OktLS4XEYC+99JK4IUUEEeRaLBa73W6322fl88CK8XJszHNFkPv333/jhZSUlFnTAzJbuF96enrwglwuLykpEYSq1Wohg1Vs3BUT4QrN6XQKt3FxmsD+/n6VShU4FHz++efRDyziiHNC++CDDwKTWmo0mkCzDocDLiVjNBHn3sLw8HBFRUV+fv6aNWuEB2g8z589e7azs3NW+p+QScIC4Xn+wRxGRHsSgbOCORwOtVptsVgGBgbmSoAbMklYIGG2FZcHYp4bq4j/aN3tdofPK3zHm5CgOYnvB/Hljo6Ohte3cO/wkmEBECIXECIXECIXECIXECIXEPCpWFZWllQqhd5LGDIyMsTaNbhcg8EAvYsHFjIsAELkAkLkAkLkAkLkAkLkAkLkAkLkAkLkAkLkAkLkAkLkAkLkAgIod/v27enp6enp6ampqY899hhevnbt2v20+euvv97tbbbBwUGxfkoNeMvxo48+wgu5ubnNzc2rV6++/zazsrIW0JN2EYaF7u5uvV6v1WrLy8uvXLmCEHK5XNXV1e+9997GjRtHRkbMZnNdXd3atWtNJlNXV1dhYWFWVlZDQwNCqL+/H7+RMjIyUl1dbbVa8/LycnNzu7q6cONHjx7Nzc194oknNm/ePDQ0FP2jCyTacm/cuFFeXl5fX9/V1bV8+fKKigqE0OTkpMPhGB8f37dv39TUlN1uX7dundPp9Pv9VVVVhw4dstlsR44cuXnzptDO1NTUZ599plAonE7nli1b9u3bhxAaHx9vamo6ePDgTz/9pFar29raonx0s4j2L26+/fbbdevW4SHi9ddfX7VqlZAKaPfu3QzDXLhwYfHixc8//zxN09nZ2ZOTk0qlUqlUJicnCz9Jx0gkkm3btlEUtWHDhlOnTiGE4uLinE7nww8/PDY2xjDMjRs3onx0s4i23MuXL3///fcvvvgi/s9ly5bh/rh06VIhz01CQgJOK8QwzOLFi3GhkGhIIDExUVhNWOfgwYOdnZ0JCQlxcXGLFi2CP6BwRFtuYmJidna21WpFCHm93r6+PqVSee3aNZa960iCM+KcOnXqhx9+aG9vVyqVHR0dZ86ciUzQ90q0x9z8/Pyenp7e3t7p6en333+/ubk5go3fvHlz0aJF8fHx4+Pj7e3toufEibbcpUuXvvvuu7t27dJqtb29vY2NjRFsfNOmTRRF5eTk7NixY/v27b/88suXX34ZwfbvFmpycnJqampiYsLj8SxfvlzEUBYWIyMjHMfFx8dLpVKWZUMm7iKXv4AQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYAQuYCEuMVLuCvCCKRxNVF8D9zRGy2sF5V4Yoo7SqOp2zAMI/rj0oXC9PQ0y7JUACFXYymKommaZVmO49xut9frjXKgCxGWZePi4hBCIZ9L/n813GcZhuF5fmxszO12T0xMhP9I2n8ZiqLi4+NVKhVFUTKZjGGYMJ33Vs/lOE4qlSoUCpZlPR7PzMwM8RsMlshxnEwmk0qlHMeF77mU3+/3+/0+n8/r9Xo8Hp/P5/P5EEJEbjDYI/4fneM4lmUZhgnjl0W3f+NGURTLstg1riN+AxEM0jSNheKFcJsIv+DEf5IB4Y4EDrLhZ2NUoEqidf7M58rgfw5e6X1jgSOXAAAAAElFTkSuQmCC" } }, "cell_type": "markdown", "metadata": {}, "source": [ "\n", "If you want to change the code you can do it in the filesystem. To access from Jupyter you can do it from the left panel. Select your file inside folder openmp and modify it (do not forget to save it with File/save). \n", "Do not forget that you will need to compile it. You can reuse the previous code above or run the same commands directlyl in the terminal.\n", "\n", "You can launch a terminal directly from jupyter launcher or just from docker (if from docker you can sue the `bash` command from docker to get a proper bash terminal). \n", "\n", "To do it from jupyter, start a Terminal in the Launcher tab. You can use the terminal to launchany command, including slurm jobs via commands.\n", "\n", "![image8.png](attachment:1cc74176-2955-4a1e-9f85-d501faa6dff4.png)\n", "\n", "Try to change the number of THREADS with `export OMP_NUM_THREADS=4` You do not need tocompile the program again. \n", "\n", "```\n", "cd ./openmp\n", "gcc -o omp_helloc -fopenmp omp_hello.c\n", "export OMP_NUM_THREADS=4\n", "./omp_helloc\n", "```" ] }, { "cell_type": "code", "execution_count": 5, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Compilation successful, executable 'omp_helloc' created.\n", "OMP_NUM_THREADS set to 4.\n", "Running the program...\n", "Output: Hello World! from thread = 0\n", "Number of threads = 4\n", "Hello World! from thread = 3\n", "Hello World! from thread = 2\n", "Hello World! from thread = 1\n", "\n" ] } ], "source": [ "# Check if the executable was created\n", "if os.path.exists(executable_name):\n", " print(f\"Compilation successful, executable '{executable_name}' created.\")\n", " \n", " # Set the number of threads for OpenMP\n", " os.environ[\"OMP_NUM_THREADS\"] = \"4\"\n", " print(\"OMP_NUM_THREADS set to 4.\")\n", " \n", " # Run the compiled executable\n", " run_command = f\"./{executable_name}\"\n", " run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", " \n", " # Print the output and error (if any) after running the executable\n", " print(\"Running the program...\")\n", " if run_process.stdout:\n", " print(\"Output:\", run_process.stdout)\n", " if run_process.stderr:\n", " print(\"Error:\", run_process.stderr)\n", "else:\n", " print(\"Compilation failed.\")" ] }, { "attachments": { "f2183b4a-a55e-4338-ab61-8c10f015419d.png": { "image/png": "iVBORw0KGgoAAAANSUhEUgAAAdQAAAIaCAYAAACZLbw1AAAAAXNSR0IArs4c6QAAAARnQU1BAACxjwv8YQUAAAAJcEhZcwAADsMAAA7DAcdvqGQAAEVMSURBVHhe7d0LlBTVoe7xPQMoKCAKemFGBI0PEoXknCCiMfEVFR85Jr4IyfJEI1yj0UQGFU2M4ivJVUCvXLP0qqhXPRE1Hs1RI+LK8pWIoiYq5ohgRGEAERQQBBGYO9+mdrspunv6UV1d1f3/6V717Ac93fXVrtq1q2HSH19pW7vkHfPLMacYoFJaW1vNzJkzzYIFC8zGjRuDucBmnTp1Mv379zfDhw83zc3NwVwgXQhUVNw999xjxo8fH0wB+U2cONGMGjUqmALSg0BFRS1atMjsv//+dnzPPfc0Rx55pOnWrZudBpy1a9eaGTNmmHnz5tnpWbNmmaamJjsOpAWBiop66KGHzHnnnWf22msv8/TTTwdzgewOPfRQM3fuXDNlyhRz4oknBnOBdGgMhkBF6JypfPvb37ZDIB/3PXHfGyBNCFRU1IYNG+yQw7wohPueuO8NkCYEKgAAESBQAQCIAIEKAEAECFQAACJAoAIAEIHGhoaG9oEKAAAoFTVU1DztNG7ecdxyHACi1NjW1tY+UAEAAKWihoq65GqquWquxSz354s/z18nV3Fyze9ItseF5+Uq/roAykOgoqb5QZErNDR/85GaL9Zx0+IvdzTtirjH+Y934+I/3o2HH6tpV8R/fC7hx4rmuXFx4/48x1+3kNcDkBuBipqWLVgk13g2brm/nsLHlVw6et6wQp4zasW+RwC50coXNc0Pp1zjxXKPVRhFFUiVeE4A8aKGiprmh1Ou8XLCNZ9KPW+U0vAegbQgUFH3FK5+DVH8oNG4P+2vE17PX1ZKaGd7znyyvRfN6+hxjr+u/34BFI9ABdopTPxAcdN+8WVbruIv82Vbxw07Kh3Jtn62aTd04062eQCKR6Ci5vmB4cb9Gpxfu4uCez73nEkLK//f6r9PAOUhUFGXXLD6JSqVet6ohN9fEt8jkEYEKgAAESBQAQCIAIEKAEAECFSgSlyDoGwNg/Ity6fUxwEoH4EKVEm+BkGlNhYq9XEAykegAu3CtbpsNTx/HX9ZeF6+5f78clTiOQGUh0AF2vm1OgWUm/bDytX+wstyPdbJ9bhS+a8b1XMCKB+BCoS4kApTaLmSi3us/xyFPK4UlXhOAKUjUIECuODya4WFKPVxhXDPWYnnBlA8AhUISWOtj5oqUH0EKhCi2p5fs/SHmu+HV0fTHT0u27zwuPjT4edUKfT9AagcAhXIQgHlQspx8wopvmzL85V8j3EKne8KgMojUIF21OoAlItABdpRqwNQLgIVAIAIEKgAAESAQAUAIAIEKgAAEWg0tL0AAKBs1FABAIhAo66244o7AADKQw0VAIAIEKgAAESAQAUAIAIEKgAAESBQUVGdO3e2w7Vr19ohkI/7nrjvDZAmBCoqqn///nb41FNP2SGQj/ueuO8NkCYN1//x1bZPl7xjfjHm5GAWEJ1FixaZ/fff344PGjTIHH744aZr1652GnBUM50xY4aZN2+enZ41a5Zpamqy40BaEKiouHvuuceMHz8+mALymzhxohk1alQwBaQHgYpYtLa2mpkzZ5oFCxaYjRs3BnPr2+TJk01LS0swVd86depkD/MeeOCB1EyRWgQqUCXNzc12RwNAbaBREgAAESBQAQCIAIEKAEAECFQAACJAoAIAEAECFQCACBCoAABEgEAFACACBCoAABFoNA3BGAAAKFljgwKVUAUAoCwc8gUAIAIEKgAAESBQAQCIAIEKAEAECFQAACJAoAIAEAECFQCACBCoAABEgEAFACACBCoAABEgUAEAiACBCgBABAhUAAAiQKACABABAhUAgAgQqAAARIBABQAgAgQqAAARIFABAIgAgQoAQAQIVAAAIkCgAgAQAQIVAIAIEKgAAESAQAUAIAIEKgAAESBQAQCIAIEKAEAECFQgJs8++6zZZ599zAMPPBDM2UzTmv/MM88EcwCkUcMNj77atmbxO+YXo08OZgGolN1339106tTJdO3a1Xz88cdmxx13NOvWrTMbNmww8+fPD9YCkEbUUIEYjRs3zoanwlQ01LTmA0i3xoaGBtP+P4AYnHvuuaaxccv9WP0GzzvvvGAKQFpRQwVi1tLSYrp06WLHNdQ0gPQjUIGY+bVUaqdA7SBQgSpQrbRz587UToEa0vC/H/tb25rF88wlZ9LKF5XT2tpqZs6caRYsWGA2btwYzK1f+gxmzJhhjjzySNvqt97pM+jfv78ZPny4aW5uDuYC6UKgouLuueceM378+GAKyG/ixIlm1KhRwRSQHgQqKmrRokVm//33t+N77rmnrZF169bNTgPO2rVrbY193rx5dnrWrFmmqanJjgNpQaCioh566CHb6GavvfYyTz/9dDAXyO7QQw81c+fONVOmTDEnnnhiMBdIBxoloaJ0zlS+/e1v2yGQj/ueuO8NkCYEKipKvQAJh3lRCPc9cd8bIE0IVAAAIkCgAgAQAQIVAIAIEKgAAESAQAUAIAIEKgAAESBQAQCIAIEKAEAECFQAACJAoAIAEAECFQCACBCoAABEgEAFACACBCoAABEgUJEqDQ0NtoTHUR73WfJ5AqUjUIE650K0ra3NFgClIVCReuHalT8uxSz354s/z18nV3Fyze9ItseF5+Uq/rqF8tcNP9ZN55vvTwP1jkBFavgb7VwbcM13tSy3jl/r8pc7rmYWfpz/eDcu/uPdePixmnZF/MfnEn6saJ4bFzfuz3P8dQt5PQk/d/jxueY54fcH1DMCFanhb7gLGc/GLffXUyi4kktHzxtWyHNGrdj3GIVsnydQrwhUpIYfTrnGi+Ueq0CIKhQq8ZwAko9ARWr44ZRrvJxwzadSzxulNLxHoJYRqKgpCle/hih+0Gjcn/bXCa/nLysltLM9Zz7Z3ovmdfQ4x1/Xf7/5+M8dfl3JNc/xlwP1rtH+INr/A2qFNvx+oLhpv/iyLVfxl/myreOGHZWOZFs/27QbunEn27x83Pp+cQqd7y8D6lmj/UG0/wekgb8Bd+OVrDG553PP6V47Kfx/q/8+AcSPQ75IPResfolKpZ43KuH3l8T3CNQLAhUAgAgQqAAARIBABQAgAgQqAAARIFABAIgA16ECABABaqgAAESAQAUAIAIEKgAAESBQAQCIAIEKAEAECFQAACJAoAIAEAECFQCACBCoAABEgEAFACACBCoAABFoNNzgHxXUuXNnO1y7dq0dAvm474n73gBp0ki3+Kik/v372+FTTz1lh0A+7nvivjdAmjRMeezvbasXzzMXn3lSMAuIzqJFi8z+++9vxwcNGmQOP/xw07VrVztdr1QLW7hwoenTp4/Zcccdg7m5LV261Hz44YemV69etmy//fbBktqhz2TGjBlm3rx5dnrWrFmmqanJjgNpQaCi4u655x4zfvz4YKo+tbW1Gd0qUUPReKnCzxHFcybJxIkTzahRo4IpID0IVMSitbXVzJw50yxYsMBs3LgxmFubPvnkE/vv1L9ZNdGPP/44WPKFXXbZxQwZMsSWF154wZYDDzzQlrC5c+eat956y6xYscKWzz//PFiytW222cbWYlXzDQ+7desWrJU8nTp1sod59e+nZoq0IlCBMv3zn/80L774og1F7TQoSH0Ki8GDB9uwOOCAA+ywe/fuwVJjJk+ebCZNmmTGjRtnWlpagrm5LV++3L7m/PnzzbvvvpsZqijMc+nZs6cZOHCg2X333c0ee+xhh5red9996/4wPBAFAhUokmqMCk4FqIJ0yZIlwZLNVEv8l3/5Fxucw4cPN0OHDs1bOyw2UPMpNWz79u1rw9UFrgtbBW+Sa7ZAkhCoQB46P/nmm2/aAHUlfAhXtbuvf/3rNjxVNL7tttsGSzsWZaDmo/ftwlbFjetw8rp164K1trbzzjtvEbIqAwYMMHvuuWdNNpACSkWgAh6d3509e3am9qmycuXKYOlmOlw7bNiwTIDqPGiXLl2CpcWLK1Bz0U7DBx98sEVt1h/Pdw1x7969twhbv2bbo0ePYC2gPhCoqGtq4PO3v/0tc/7z5ZdfNp9++mmwdLMddtjBnvt05z91PrSxMbpOxqodqB3RZTt+jdYP2zVr1gRrbU0Nofyg9cNWnylQawhU1BUd2nz11Vczh29feeWVrQ539unTJ1P7VIDus88+Fb0kJemBmk+pYauWxwrXcNhquNNOOwVrAelCoKKm6XClC0+Vv//972bDhg3B0s3UIMfVPhWie+21V7AkHmkO1HyWLVtmg9WFrB+2+RpI6VCxH7J+6GpnB0gqAhU1ZdWqVZlznzqM+8Ybb2x13asa1LgaqMpuu+0WLKmOWg3UfHI1kFLRtba5qBFUrrDVtb1ANRGoSDVtmP/yl79kaqD//d//HSz5wpe+9KVMDfTggw9O3Ia3HgM1HzUCczXZcM02WycZji7vcUEbDl0dhaiVnqSQXAQqUkXn7FwDIg11TWjYl7/85UztUyGqlqhJRqAWToeK33nnnaLDVpc2hWu0brxfv36ELSJBoCLR1Ln+888/n6mBvvfee8GSzdTa9itf+Urm/OdBBx1kewRKEwI1GgpbF64ubFV0OFkdXuSia4Z1GsAFrB+66gYxyhbdpVKtnZbRyUegIlG08XPnPxWg4W78dJ/Mr33ta5kaqO5k43fjl0YEauWpxXE4bN247uSTi3q9Uh/DutTHr+FquOuuu9puJeNw2WWX2XP9o0ePDuYgiQhUVJV66XHhqaKWob5wN34K0Frrd5ZArS61BM91GDlf2GrnTiHngtYPXYVwlDdJf+KJJ8yZZ55pfwfXX38994tNKAIVsdm0aZP5xz/+kQlPlfB5r+222872fevOf371q18tqhu/NCJQk0thm6s1crgPZ5+7e47C1T+MrKFCuJSetXQ/YR3W1ikNheqIESOCJUgKAhUVo8tVdN2nC8+XXnrJrF69Oli6WbgbPx3OjeswWlIQqOmkDkH82qwb11Dn/nPROdnm5ubMeVpXq1UNV2GrozLZnH/++eaBBx4Ipow5+uijbbBybjU5CFRE5rPPPjOvvfZa5hButm781B2dC08VNShKQqOPaiJQa49+C2pAp3AN13AVtu6m8GFqbayGUH7YuuHbb79tfvKTnwRrbqba6u23324b46H6CFSUTHvos2bNsuGpEFWfuOvXrw+WbtYn1I2fDlthSwRq/VE4KnB17tYP23AjvDAFrsLYBbK73EeNlfTdobZaXQQqCqbDtS5AVbJ146dDWS481ZmCDmMhPwIVjnZI33///S0OIbvxBQsW2HYILlTD186q1bFqq/vtt18wZ/N12/rNzpkzJ2etuJ7pM9ROvk47aee/XAQqclI3fn/9618zNVA1KNIP2ud346deiHS4CsUhUFGIM844wzz55JNbBaMfrDqF8uCDD9p2CJdeeukW51yR36hRo8yECRPKugyPQEWGLn73L2HJ1o2fOo53l7BoSP+p5SNQ0ZFp06bl/G4oRE899VTb6lcti9UJxFFHHWUWLlxojxCp1byOHIVrtNh8L2AdZlctXkcCVCF46KGHSr4siUCtYzocpF6IFKLqTEHnc8L8bvy+8Y1v2EZFiBaBinx0qFcBqSNGTjhEfRdccIH5/e9/b8466yzbIQQKoxr9HXfcYY+0aQemFARqHdG5GVf7VAl346fDRLp5tjv/qZK2bvzSiEBFPieddJL9veYLUUe1LZ0P1PlU7SSjOPrs9Bl21Dgsl/q+XqHGqeP4u+++25xzzjnm61//ug3KsWPH2r0vhal6ctHhoHPPPdfcc889tuHCY489ZvfUjjzySMIUqDK1YVCAKlBnzJhhxowZk/dwpA5dimpZKJ6OwpWDQK0SneeIks4FqBs/HbLQoR71MHTooYeaiy++2DzyyCO2Vxd12acvjGpCaqygANWySy65xBx22GH29lcAkkPXl3YUoj5deiO6gw6Kp3PN5SBQq2D27Nnm5JNPDqZKo9a26kTh5ptvtq3/9t13X3PEEUfY2uWjjz5q+8RVN37f+ta3zEUXXWT+8z//0wbu/fffbw8r6odaa33iAvXOtQCmAVJpyv3cCNSYqZPrU045xZ7jKMbnn39uXnnlFXPTTTeZ0047zTYWOvbYY81VV11lm9K72zup8cKvfvUr8/jjj9sAVeOEn//85/bcQCn9hwIACkOgxujWW2+1d4xQa72OugpT12U6f6IGK2qIoIuP/+3f/s38+te/Nn/+859tJwtqcXvMMceYK664wkyfPt28+eab9pCvuifTId966xMXAKopZytfetjIr9geNsIdW2vcD1Xd1UJ936rxQa5u/Pr27Wtb3rrrQHVNKNKPVr6Iir5H+j7pe6TvE4rjPr9SW/k2/J/HX2tbvWiuGR8Eqmo+9LBRnHw9bOhQrGqlCkmfdlTc9Z8avvHGG/buLD668asPBCqiQqCWJ9JApYeNwoV72FArvKeeemqLUNUF2QpTHYrV+u5zVGOh8F1YRJ+5aq26ibaGdONXHwhURIVALU+5gWoUqL+97cH27X1bW/sfoK19I952xRVX2GkU5pe//KX93MaPHx/MaWtrr3G2DRo0yM7v16+fLRp30xoecsghbRdffHHbww8/3LZs2bLgkag37T9i+33QECjHxIkT7XdJQxTPfX6lyjRKUiKrRahan9JdVXGuvvpqW5O/++67zeLFi23HCbr5r+sqzNVM2z/vTE31u9/9rnn66afNb37zG3PCCSeY3r1723UAAOmUCVR62CiP62Hj2Weftdd69ujRw047ClH/0Hl7rdS2+gUA1IZMoLoeNsrtKaJeuc9Nd+P/wx/+YK8B1aUsaqyk607dcj9UtazUTpgBAMmSCVQdikTpXFD69wvVjX7VbdgNN9xgXnrpJXs/Ud0AWA2V1HpXFKrqOQkAkG507BAj9WSkjq6vvPJKW4vVeWsFrFoBAwDSjUCtMl0eM3LkyGAKAJBWBCoAABEgUAEAiACBCgAoSvgywEpzrxfna5aCQAUAFMV1UhMHF6Lu9ZIcqgQqAKAgfk0xycFWLQQqAKAgpdZMw0Hsl1pCoAIAKsoFcbbSEbdOGsKXQAUAVFS4VuqXQhQavtVGoAIAKsoFYrZSKBe+xTwmbgQqECPdDEF3IyqE1uXmCUiScK2ymFpmqfzXSHKYCoEKxEh9Oet+wwcccEDOYFWIavnll19u1weSwq9Z+qWS4nqdKBCoQIx0gwTdgWjhwoVm7NixNjjd3YY01HRLS4tdrvW0PoB0iD1Q4zhEEFaN1wRyGT16dOYG9ApO3TdXNNS0aLnWA5AesQdqnFV3ghRJ5Gqp4v8e/HFqp0D6ZAK10iHnwi3OkPM3UECSuFqq+y2476mmqZ0C6RRbDbXUcPNDOFyAtPJrqeJ/n6mdAumU+EZJLoizFSDNwrVUDamdIqmqUZHJ9ZpuftzvpyOJD1T/gwsXIM3CtVShdoqkirMik28b7+a795KkLKCGClSRq6UKtVMkkQs3V+KQ1m18bIEa/mPE8cepxmsCxfBrqdROkUSlhpvb3mYrtarh/zz+WtvqRXNNp4/fNddff70ZN26cvbAcxZk0aZKZPHmy/ez0GSJZli5dambNmmXmzJmTuD3fdevWmbvvvtucdtpppmvXrsHceGkjN2jQIDNs2DDTp0+fYC7SppLbIReEcf5+sr2mPy/q9+Q+v9bW1mBOcQjUiBCoybR69Wpz6aWXmgceeCCYg46MGjXKTJgwwXTv3j2Yg7RIUqC69bMp9jkI1DpDoCbPypUrzVFHHWV7H9pjjz3M0KFDTXNzc94fer3SBkkbEdXi3333XdO/f3/z1FNPEaopk6RAjULaAtXc9KfX2357+x/arrvuurampqa29idsf28o1sSJE+3npyGSoX2DYv8mV1xxRTAHhfjlL39pP7fx48cHc5AWldgOtcdE1lJJ2V5Pxck2Lwru8ytV4lv5AqXQHubvf/97s+uuu9q7u6BwV199ta3J67zu4sWLg7moV+05kbVUUrbXU3GyzUsCAhU1SYcu5eCDD7ZDFOcb3/iGHb7yyit2CKBjjTbhY0x5HfN2x73j4F4vztdE9f3zn/+0w379+tkhiqMaqsydO9cOAXQs9hpqnNV0F6Lu9QjV+sHfvDzuc9u0aZMdAuhY7B07uAIAQC2JLVBLrZmGg9gvHSn1NQEAKFajDaYCwqlaXChmK4Vy4VvMYwAAKEbiW/n6NdJwKYRbjzAFgNIVs92NSr7XrMb76UjiA9WvkYZLR9yHXci6AIDcCt3uRiFtQepkAtV9UJV6o+EPIc4Pxb1WXK8HALXC337GtQ3NF95xBnuxYm+UFC6VFPfrAUCtKXXbGQ5iv9SqxB/yBQCkj1+RCZdaRaACACKXrWbqSq0iUAEAkctWM3WlVhGoAICcwrXKOGqZ+V4z37JqI1ABADllq2GqVFK211PpaFm1EagAAEQg9kCNu3ruXi8phwQAALUp9kCNs3quEPVfj1BF1OLcWXOv5RcAyRFboFZjQ5CU4+qoXXHuIDruNfl+A8kSW6CWugEIB7FfCuGvywYIUfG/h+77FZdqvCaAjiW+UZIL4mylEP66bIQQlWK+gz4XhtlKIfg+o1qK+Z5GJddruvlxv5+OJD5Q/Q8uXIC0cYGYrXSkkHWASin0exqFfNt4N9+9lyRlQU3XUAldJI3bUGQrQBJV43ta6DY+aWJvlOTE8cfRH8R/nTT+gVBb3IYiW+lIpX8vQDaFfj/D3LY3WylHqe8nDrE3SgqXSovztVA/whuGKDYUHdF32H8dvtNIMn/bGy5RSOLvIPGHfIEkCm8gXKm0OF8LKIfb+ctWyuWeI2m/g0ygujcWxT8WAFDf/J2/cClHUsNUqKECAHIK1yrD05VQyGu6eeH51USgAgByCtcuXamkbK+nkmtZUhCoAABEIPZArUYVPWmHBQAAtSf2QI27ik6QopKquYPIdxtIltgC1d8IxLUh0Osk6fg6ak+1dhDjfl0AHYstUEvdAPghHC5AtVTju+hehyAFkinxjZJcEGcr+Wjj09E6QKkK+Q5m44dwuBSq2PUBxCPxgepvcMKlI+H1CnkMUEkuiLOVQrl1+T4DyVKzNdRs63X0GKDS3E5etgIg3WJvlOTEtREJvyZQTf6OXrgASLfYGyWFS6XF/XqoD+EdwvB0Jbjvr3sdvs9AsiT+kC+QRP5Oml8qLc7XAlCc9kDd1D5oM42Nm7N10yZNAwCAYlBDBQAgAgQqAAARIFABAIgAgQoAQAQIVAAAIkCgAmWI4/pTx72WXwAkB4EKlCHua0K5BhVILgIVKEE1aooEKZBsBCpQglJriuEg9guAdCNQgRi5IM5WCuXCt5jHAKg8AhWIUbhW6hegXO57xM5Wacr93BrtjzmYAFBZrjaarQDlGjhwoB0uXbrUDlGcJUuWBGOloYYKlCBcqwxPA9Ww33772eFrr71mhyjOq6++GoyVhkAFSpCthqkShzhfC+my9957m8MOO8zMnj3bXHPNNcFcFOKKK64wc+bMMd/4xjeCOcVr+N0Tr7V90jrXNH70rrn++uvNuHHjTEtLS7AYhZo0aZKZPHmy/ez0GaK6+HuUh88vvT766CMzYsQI09raavbYYw8zdOhQ09zczBGULLRjunDhQvPyyy+bd9991/Tr1888/PDDZtdddw3WKA6BGhE2QMnC36M8fH7ptnr1anP55Zeb++67L5iDjowcOdJceeWVpnv37sGc4hGoEWEDlCz8PcrD51cbli1bZl588UV7KLOSpwleeOEFWw488EBb0kK19kGDBplhw4aZPn36BHPLoED9X7c/2Hbddde1NTU1tbX/kNo/dxRr4sSJ9vPTENXH36M8fH4ohnKD/Ghro1ESAAARIFCBMsR9uYx7vThfE0BhMoHa2Ei2lqO9tm+HbOjqi/7u7m9fae67xXcNSCYbo/pZDhgwwM54//337RDFcT1s7L777naI2uZqia4AQKZaOnjwYDt89tlnzaeffmrHUbi//e1vdjhkyBA7RG0rtWYaDmK/dCRcM42rZgygMJlAVQ8bhx56qPnggw/Mz372M7NmzZpgCTqiHjbeeustc8QRR5gvfelLwVxgay6Is5WOhIO0kBAGEJ+Gm594rW1V61xz4Y9P2qKHjZ133tl885vftIeC+eFuTRs1v4cN9awxffp006tXr2ANVFNc11EWW1vM91vq6Dn81yr2dYvFdagohr4r+s7ou6LvTL3aIlCFHjaKF0UPG4hWUgO1HAQqkopA3WyrQHXi6mGjWEnpkUMbtEh72ECkKh0ILtDCKv1b8V+3kq9FoKIYBGpAgXrt7Q+2/zbTof2PRo8c6BA9/ZSHzw/FYLu8GRefAgAQAQIVAIAIEKgAAESAQAUAIAIEKgAAESBQAQCIAIEKAEAECFQAACJAoAIAEAECFQCACBCoAABEgEAFACACBCoAABEgUAEAiACBCgBABAhUAAAiQKACABABAhUAgAgQqAAARIBABQAgAgQqAAARIFABAIgAgYqa1NDQYIdtbW12iOK4z819jgA6RqCiJg0cONAOly5daocozpIlS+xw9913t0MAHSNQUZP2228/O3zttdfsEMV59dVX7XDIkCF2CKBjBCpq0t57720OO+wwM3v2bHPNNdcEc1GIK664wsyZM8ccccQR5ktf+lIwF0BHGm5+4rW2Va1zzYU/PimYlWyTJ082kyZNMuPGjTMtLS3BXGBrH330kRkxYoRpbW01e+yxhxk6dKhpbm7mvGAWOme6cOFC8/LLL5t3333X7Lrrrmb69OmmV69ewRpAbmyXNyNQUdNWr15tLr/8cnPfffcFc9CRkSNHmiuvvNJ07949mAPkx3Z5MwIVdWHZsmXmxRdftIcyk9Dy94UXXrDlwAMPtKXaVGsfNGiQGTZsmOnTp08wFygM2+WAAvXa2x9s38akQ/sfra2pqckOgbTie4xawvd5MxolAQAQAQIVAIAIEKgAAESAQAUAIAIEKgAAESBQAQCIQKOuP6PnGAAAykMNFQCACBCoAABEgEAFACACBCoAABEgUAEAiACBCgBABAhUAAAiQKACABABAhUAgAgQqAAARIBABQAgAgQqAAARIFABAIgAgQoAQAQIVAAAIkCgAgAQAQIVAIAIEKgAAESAQAUqbNq0aeb+++8PpvLTuipAUvF9zo1ABSpsxIgR5rLLLjMHHHBAzg2RNjpafvnll9v1gaTi+5wbgQpU2A477GDGjBljFi5caMaOHWs3NLNnz7bLNNR0S0uLXa71tD6QVHyfcyNQgRiMHj3a9OjRw45rQzN9+nQ7rqGmRcu1HpB0fJ+zI1CBGLi9emlra7MlPE7tFGnB9zk7AhWIidurb2hosNNuw6NpaqdIG77PWyNQgZj4e/XiNkRC7RRpw/d5awQqEKPwXn09780j/fg+b4lABWIU3qsXaqdIK77PWyJQgZi5vXqhdoq04/v8hUQHKj1yoBb5e/XUTpF2fJ+/kOhApUcO1CrtxTc3N1M7RU3g+7xZwy3TX29b1TrXXHDGicGsZJk0aZKZPHmyHd91113Nvvvuay8ePvroo82bb76ZuYhYPXOMGzfOjgNpsGDBAtO/f/9gCqX69NNPzYYNG8zGjRvN559/nhn3h9nmNTY2blE6deqUdZ4a2rhlbtqNh9d14127dg3eXf3g++wCddE8c8Hp3wtmJcvKlSttDfSTTz4J5mxNx+1ffPFFDp0BFaDf3rp168xnn31mS0fj/jw3nW2ewi8cgNmCzy+ap8enTbdu3cy2225ryzbbbGOLQldDNy/bsJBlKnoulZ49e9rtoSuIV+IDVVwt1b9w2B+ndgp8YfXq1TYEXVENbsWKFXb+qlWrtlr+3nvvbRV2bpgGChLVDjt37pwp/rQbD6+jcNZ2RMNNmzblnHbjGrriprOtn6TPrXv37pmQVYVj++23t9Nuvr9cxY27+b179w6eCYVIRaD6tVR9YR13zRO1U9SapUuXmo8++mirokD0wzBbSEZtu+22y9SAXM1IxU0XMj/XeK7AyxWCKqrtpY3+LuvXr8/stGjcTftDhbG/LLzcn6fir79mzZrMd0Bl7dq1wauXT8HqQlfb2h133NGWnXbaKTPs06dPZpmmFcr1JhWBKn4t1dVQqZ0iDT7++OOs4egX1SA//PBDO15uKCqw/FqHil8jcTUVt2zAgAGZgFNxhycVpEg3fff8nS63Q+amdfRC67gQ9tfTUN/Lcuyyyy42YBXIvXr1skHrQjgcyBqmvWKUCdT+3dabBx54wP7o9I9zexvhf7Abxi3buVRtDKidIk5+OLpxDfX9XLZsWSYcly9fbouWlcL91lzRBkm/yXA4uqELR220gCgpdMOBq+92+DegoT+umnQp9F13OfP973/fjBw5MliSfJlAbVj+z0xr2kL4P3g37vZC3HR4o1Auv8WvUDtFOVzghTcMLhD9+W68FAo8/3eg4jYa/rR+L24I1ILW1lb7uwn/jnKNhw9Tp20bv1WgDh8+3Bx00EF2ofa6/X+0G+pYfSlc2GpPW4eTdNhJRRscfzpb0XKd+P/Od75j95SondYn7R2r6DuoPWcNVTTPn85VXFDqu10KfVf9HUY37k+7UNS8vn37Bo8EUIjFixebm2++2dx2223pD9RC/wEffPDBVkGroRsPz9ehgiipcYLCVBs4P3Q1dPM0raJzQio6t+TGc01zyKx8quFpT1MNJjR0Jde0glDFBaWKC0d/ntaPkju94cKvo6HOBwGoPHc0sm4CtRQ6x+RCVwHrbzhzFW1wVSN10xp3x+bVKKlSFMThwNU812jDFbeOhuGLvPX+NPSn3Xh4XX/azcv2eA1d8/xwc/3wtBvX0BU3Xcjj/QAMj+vv5s9zpdL0Ofs7TRrq89e4m3Y7VuGioxoKRxUdJQGQTARqjNQjhzaKhRz607gLAX/Dn2taj0d5XMj5Oxz5pl0AZgtDTfvhCaD2Eag1RjXhbIEbHnfTug5MPbm4mqArrtYXns5XQ/RLtnnZarPZ5pVTQ9YhddcDSzgAc02rBggA5UptoP7fJ99oW9k6l0AFACRCWgOV+6ECABABAhUAgAgQqAAARIBABQAgAgQqAAARIFABAIgAgQoAQAQIVAAAIkCgAgAQAQIVAIAIEKgAAESAQEWqqIN/lSj5z1no84fXy/WYQp+vVJV+fgCFI1ABj+76o9IRf71qBlqh7xdA5RGoSC2/dubGw9NOvmW+8DI3nW++449nE15f3Lzwsmzz881z/OWFzAcQHQIVqaeA8Gtp/nQ4PPItC3PL/Vpg+DH+6/rjYdle181zxc3z+cucbPPEPdZfXsjzAYgGgYrUCwdEvsAoJ0zKCaNsj3PzFHrh4AOQPgQqUEV+rTIqBDRQHQQqUCWVCFPR8/kFQDwIVNSVcmpu5dT8qlFjLOf9Aiheo9EOLDuxqBOqsbmQ6aj25pb7wZTtMf56uWR73WzPX45sz+fmAai8Rv3syv8pA/FQQPiB5AdGR9NOvvVyLcs13wlPO/78bOu4eX7x5/sKmeemc80HUDkc8gUAIAIEKuoCNTQAlUagAgAQAQIVAIAIEKgAAESAQAUAIAKNaqZBUw0AAMrTaC9C5UJUAADKwiFfAAAiQKACABCBRtvvZzABAABKs7lzfAAAUBY6xwcAIAKcQwUAIAIEKgAAEWi47cnZbStb3zZty/9pJk+ebFpaWsy4ceOCxQBQvpUrV5q1a9fa8umnn9rh+vXrzeeff242bNhgNm7caIf+uD8v3zJ/Xvj5cq2nYWNj4xalU6dOWeep4aZb5qbdeHhdf1qlc+fOtmyzzTZm2223tUXjKl27ds3MzzVU6d69e/Ap1o9JkyalMo8IVKAOffLJJ5nSt2/frcJu3bp1mXG/aP6aNWu2mBdez59evXp18IqIQo8ePbYIW42rKJxVevbsaddR0bjC2M3bYYcdzPbbb7/F/G7dugXPnCwEKoCKU5j5YajAWrVqlR368/2igFuxYkVmXT1H3LQB18ZbZbvttrNDBYBqb6rZ+cNc8/xlChHVFP154XXC4+F1VFPVPXI13LRpU85pN66hK266kMerJv7ZZ59lhm48PF9D7bD4y1S0Y1JJvXr12iKENXSBq2X6e7nlKgrmHXfc0ZY+ffoEzxItAhVAURR0H330kS0KvA8//DAz7crHH39sli9fbseXLVsWPLJ8/kZyyZIlW4VdodP+fAWkG3fztfFFNBSsLmRd6PoBHN7Z0rS/I+WGWqahvlPl0M6CdmoUvDvttJMNVxe2mlZxwdu7d28bzpq3yy67BM+QG4EK1LnFixfbjZQ2Ygo/F4gaZivaMBZLoeVqD/7Qr0G4+dnmaUjIwafvqgthF7rhAHbFzW9tbbU7YgrVUuh76II32/Cpp54yf/7zn9MfqD7tYWb7B+cab2pqCh4JpNuiRYts6PmBmG+8lMNy2hgp7LT3vttuu9nfkcb935T2+rVnr/k61wlU2zXXXGN+97vf2fHvfve75sorr7S/Af834f9Gwss0XqjUBmpzt/Xmvvvuy/yDdZipFNqDzha2/lAbCR0W0glyFbe3AkRJ32Ud9vKLO3ya78euw2ilUOjpe+yG7jfgQnLnnXe2tUM37+abb+aoEFJj7ty55txzzzWzZ8+22++JEyeaE044IVhaHP/35//21BrcHd1RbfiUU04xI0eODB6VfJlAbTn9e8GsL+gf5P+jCxmq2Xqp1FDAhWy46A+o4PWnNVTTdG2owgHtptV4Acnmzv+Ei84x6vCSP62hm+em3Tx/WpdFlKpLly6Znb+Ohm5ch1OL5c4TXXLJJXZDBSTVHXfcYa666ip7mmLo0KHmxhtvNAMGDAiWwskbqKXQcXYXsNrbyFUjUFj7G0VNV4qCVYevXaMJV4qdVkirqXq25RqvNaqpucsf/HH9qPR3c9Ph5dnm5Vquv32lKOTcTpaKDq/6IeiG4cYU2iGLgzt0NmHCBDNmzJhgLpAcqi1ecMEFZsaMGbby8rOf/cweUVGLaWwt8kAtl0LX1TJUtOFVSIfnqUby+OOPm4ULF9rHNTc32w2jX1OpZEh3RAFbzgXhbv3w4zXM1Tw/PO3GNXTFTWdbXwFXLa7BjH+kQUXT7siEhtp5cePheW5awZgGl112mbn99tsJVCTSc889Z37605/aSpHO8atWuv/++wdLkU3iArVYd911lz0prjDQH1t7/H7jKB2CdrUhVzMqdzrbMh22rDXugnFXC3c18aim3bgOsdYjAhVJpO3Zb3/7W3PrrbfaaZ0nve666+wOK/JLfaDKnDlzzE9+8hPz9ttv20N3Oi81YsSIYGn89IUM1wjD0/lqmH7JNi9bbTbbvFJqyAo5xINARdKo4dHo0aPNvHnz7FEjBWupDY/qUU0EqijEtGG6++677fRpp51mfvWrX7FXhcRygfqb3/zG/Pu//3swF4ifdujvvPPOLRoeqRV6v379gjVQiJq524xqVtqb0gZK51IVrEceeaR5/fXXgzWAZHEdO6ihG1Atanj0/e9/31x66aX2FNn5559vHnroIcK0BDV3+zYd6lUvG9/61rfMe++9Z77zne/Y86raAwOSpJSekoAoPfnkk+bwww83zz//vG14pCC98MIL7WkgFK8m74eq61L/4z/+w+5xiS5P+MEPfmD7SgWAeqdTZBdddJE544wzbCtenSdVRYRWvOWp2RuMqwHO2Wefbf7rv/7LXoD87LPPmm9/+9vmmWeeCdYAgPqjno6OPvpoc++999qGRzqCp0J7k/LVbKA6Q4YMsRcln3jiifZcgWqqusymnB6dgCjRshpx0Gmvm266yRx33HG2Fa8aHqkDelrxRqfmA1W05zVlyhR7YbI6CrjlllvsudX58+cHawDxo1ES4qI7Ianh0a9//Ws7/Ytf/IKGRxVQF4HqnHTSSba2OnjwYPPGG2/YVsB/+MMfgqVAvHQeC6i0cMOjxx57zPaARMOj6NVVoMrAgQPtedWzzjrLdlGovinPO+8821UhANQKbdNcwyN1w/rDH/7QNjzab7/9gjUQtboLVFFXd7qoXi2Bdc2qDn2otvrSSy8FawBAeqnhkRphuoZHulvMtddeS8OjCqvLQHUOOeSQLa5Z1SFh3VJL3f0BceEcKqKibZdrePT++++bgw8+2DY8Ouqoo4I1UEl1HajiX7OqvmzVD7CCddGiRcEaQGXQKAlRUsMjXc3gNzy67777aHgUo7oPVPGvWd17773NrFmz7OGSJ554IlgDiB49JSEqjzzyiG149PLLL5s999wz0/BI2zbEh0D16JrVP/3pT7Zjfd0c/cwzzzQXX3wxrTEBJJIaHp1zzjm2uIZH06dPp+FRlRCoIX4n+7oVnDrZP+aYY+wt4gAgKdyRNNVOe/funWl4REch1UOg5uA62VfflrrP6rHHHmtvZg4A1aSGR7rht86X0vAoWQjUPJqammzHDy0tLWb9+vX2JP+Pf/xjs2LFimANoHQ0SkKxdDWCgvSGG26wl/9dffXVtuGRLv9D9RGoHVBvIuPGjbPBqtZyOj9BJ/uIAoGKYujQrrY9ruGRtkXqtIGGR8lBoBZo2LBh9hCw7tKg5ul0sg8gDmog6RoeqXe3MWPG2DDda6+9gjWQFARqEXr16mWmTp1qr/PSiX862QdQSc8995y9HMY1PNLh3QkTJtDwKKEI1BL86Ec/Mo8//ri9ZpVO9gFETUe+FJy6Q8ySJUvsNkYNj775zW8GayCJCNQS7bPPPplrVulkH6Vw51CpbcA3d+5cc/zxx5tbb73Vnl9Xw6M777yThkcpQKCWwb9m1e9k//XXXw/WAHJzHYbQKAmOriVVOw11bq/OGVzDI6QDgRoBd82q62Rf51V/97vf2TvkA0BHli1bZk4//XTbp7iOXKjh0aOPPkrDo5QhUCPid7Iv11xzjW0J/OGHH9ppAMjGNTyaMWOG6du3b6bhka4zRboQqBHyO9kfMGCAefbZZ+lkH0BWOuTvGh4tX76chkc1gECtAHWyr71N9WiiQzl0so9s6Nihfqnhkc6VquHRdtttZ28bqYZH6j8c6UWgVojujD9lyhRz44032h8MnewjjECtP2pX4RoezZs3zzY8UvuLkSNHBmsgzQjUCtPNylVbHTx4MJ3sA3VMR6t0eDfc8Einh1AbCNQYDBw40J5XPeuss+xhXzrZB+rLk08+aRsePf/88zQ8qmEEakz0w7nssstsS2Bds+o62X/ppZeCNQDUGu1AX3TRRfZaUhoe1T4CNWaHHHJI5ppVdbKvQ8KTJk2y9zhEfeEcam1T5ww6V3rvvffS8KhOEKhV4K5ZVSf722yzjf2hKVgXLVoUrIF6oHvsCl0P1hY1PLrpppvMcccdR8OjOkOgVomuWfU72Z81a5Y9BEwn+0B66aiTGh5pZ3nTpk3m/PPPp+FRHSFQq8zvZF/3PaSTfSCdwg2P1Lf3hRdeSMOjOkKgJoDfyb7Or9DJPpAe2vl1DY9WrVplTjjhBNvwaP/99w/WQL1o1KFHY1RQba6Tff0Q6WS/trles3QOHemlhkc6VeMaHun3qkLDo/pEDTVhmpqa7HnUlpYWew6GTvZrEy18002t8l3Do/fff98MHTrU7gyrdor6RaAmUKdOncy4ceNssPbr1y/Tyf4zzzwTrAGgWtTwSP10+w2PdJqGhkcgUBNs2LBhdq9X17Kp2zLVVK+88krz+eefB2sAiNMjjzxiGx69/PLLZrfddss0PNJOMECgJlyvXr3M1KlT7d6wGi/dcsst9tzq/PnzgzUAVJoaHp1zzjm2uIZHrr0D4BCoKeFfs/rGG2+Yo446yjz44IPBUqQN51DTw10jrtppz549Mw2PdEcpwEegpoh/zar2mH/+85/TyX5KEajJp1Mr1113nT1f6hoe6XIYGh4hl/ZA3dQ+4LKMtPCvWaWTfaAydNna8ccfb2644QbT2Nho7xCl86VqJAjkQg01pdw1q3SyD0Rr2rRpdidV15iq4dFjjz1mfvrTn9LwCB0iUFPMdbKvGxZrL5pO9oHSqevP008/3V4D/umnn5of/vCHdqdVndsDhSBQU049XZ199tn2Bua6Ds41oHjiiSeCNZBE7hwqd5pJhueee85eDjNjxgzb8OiOO+4w1157LQ2PUBQCtUYMGTLEbgzUgEJ72meeeaa5+OKLM13cIVnc34VGSdWlhkcTJkywd4hZsmSJOfjgg23DI7WiB4pFoNYQ7U1PmTLF3HjjjbZf0bvvvtscc8wxZs6cOcEaAJy5c+fahke33nqr6dy5s214dN9999HwCCVrD1RlKp3j1xKdR1VtdfDgwebtt982xx57rLnrrruCpQB0SFc9kKnh0Z577plpeLT5ZiFAaaih1qiBAwfa86pnnXWWPbyovW9ds0on+6hn6sJTDY/UkE/nsdXwSJee0fAIUSBQa5hubHzZZZfZlsD+Nat0sp8cnEONj9/wqHfv3pmGRzQMQ1QI1DpwyCGHZK5ZpZP9ZKCnpPjoCI1reLR8+XIaHqFiCNQ64a5ZpZP9ZHCBispSwyOdK1XDI+28XH311bbhkY7YAFEjUOuIGlyEO9k/8sgj7X1XgVrS1taWaXg0b9482/BIpzzOOOMMGh6hYgjUOuR3sq8eYX72s5+Z8847z3a4D6SdTmvo8G644dFee+0VrAFUBoFap/xO9nfYYQfb8bdqq6+//nqwBuLAOdRoPfnkk7bh0fPPP0/DI8SOQK1zrpN93ShZd9jQeVXd61GHzFA5NEqKlhoeXXTRRfaQLg2PUC0EKkxTU5M9j6pOwTdt2mSuueYa2xKYTvYrh0ZJ0VHnDDpXeu+999LwCFVFoMLSranGjRtng1Vdrz377LN0so9E01GUm266yRx33HE0PEIiEKjYwrBhw+whYO3x08k+kkr3AFbDI10GtmHDBjNmzBgaHqHqCFRspVevXmbq1KmZa1bpZL9yaCxTvHDDIx3eVccNfJaoNgIVOfnXrNLJfrRolFQ8XdblGh6tWrXKtkpXw6NvfvObwRpAdRGoyMtdsxruZH/FihXBGuiIzkNPnjzZHkJ3ch1C/+tf/2qmTZsWTMFRwyOd0/cbHt155500PEKitAeqLo/gEgnkpkNp2TrZf+mll4I1kI8uTdJhyeHDh28VrI6C9OSTTzannHKKOeigg4K52LhxY6bh0fvvv2/vCuMaHgFJEwQq0DG/k301CtF9VydNmmQ3eshPLah1mFKfl4LV7YwsXbo0E6QvvPCCHfbv398uq3f6jp144olbNDx69NFHaXiExGq4fcYbbSsWzjUtp38vmAXkp8sVbr75ZtvTkjZ06hTihhtusPdgRW5qQd3a2hpMbf4cw5d3zJw5k0Bt98gjj9jW5doJ6du3r/1+ca4UScc5VBRNIXD22WfbG5gPGDDAzJo1i072C6BaquPCVEMVoXZq7OHwc845xxYaHiFtCFSUbMiQIfZmzTosRyf7HRs5cqRpbm4OpjaHqrhaqh+49Ug7ZrocRrXT7bbbzp5vVsMj9TUNpAGBirJsv/32ZsqUKebGG2+0G0E62c/PD03/cG891051o/vrrrvO7pgtWbLENjzSuXrtgABp0h6odNGF8qmBkmqrgwcPppP9PFwt1R3u1bBHjx51WzvVd+X444+350jl/PPPtw2PdCoBSJsgUAlVlE+NknReVdesqrGS62T/ww8/DNaAqLWquBqqpuuxdqrrbXX5la4xVcMjHd248MILTZcuXYI1gHThkC8ipY2hf82q62T/mWeeCdbAqaeeamulouHo0aPteL1Qw6PTTz/d3t1I595POOEE2/BIrcWBNCNQURH+NavLli2zNdUrr7zSni+rd2pk42qpGtZTo5vnnnvONjzS6QGdc9dpARUaHqEWEKiomJ133tnWVF0n+7fccos9t0on+8bWSnUutV5qp9qRUgf2ukOMGh4NHTrU7nCpdgrUiobbZ7zZtmLh26bl9O8Gs4DoKUR/8pOf2E72XVeG6ny/HqirvDfffNOeK9S1laJekVyjpAMPPNDO69mzp23huu+++9rb59WKuXPnmnPPPdf++xsbG+3lVTrcq3vwArWEQEVs1CG8aim6HZwoNHStoW4XV0sWLFhgQ1T982pYKn0+6tdXw7Q2WrrjjjvMVVddZe+us9tuu9nLqzhXilrVHqizg0Cl60HEQ3dfUQ1FjVP69etnz6GpW760U5BqB+H+++8P5mzW+X98xXQdNMJ06buvaeja087bduAXHeB/Nv+vdti2bpX5fMmbZt1bT5gNH/zDznPUkEmfWVqCVefNL7jgAnuuVHRoV9ea6rploFbRly+qYtGiRbZ7OfWOo8OAuv5QJY2HAbVjcPvtt5v/e+ut5pPgkG63r55ithl4oOm6zwjT2K34Bjeb1q406+Y8YdbPf8Gsfe0BO69Hz57mf44ZY84888xEN+JRw6Of/vSnZvny5fYwtvp85lwp6oEN1JWtc83YHxGoiJfuUqML+lU2bdpkDwWqttrU1BSskXyqbZ8/duwWQdrj0HGmU6/oapIbVywwnzw9aYtgveH66+1t4ZJEh/QVnre271iIGh7pJgo6CgHUA1r5ompUG1UPQepUXxtd1VZ1zapCKg10eFe1RYXpNgOGm97/c7rp9d0bIg1T0fPpeXf60QP2dfR6et3bbrstWKP61PBI53oVpp07d7Y3oldHDYQp6kmnE/79nAmfffKROfBrXw5mAfHS5SM6R/jOO+/Y1rB//OMfbe9KBx98sN04J40O8V5yySWZQOt59ASzw/H/y3TqsYudrpTO7cG63ddGmsauPc1n7zxtnn76abNw4ULbSlgtp6tBLZXVgb2up9XfTA2PdDN1dSeoQ/lAPeEbj0RQS9+pU6dmrllVS+BjjjkmcZ3sK0zVkb0aHjVs28PWGrcfvrmThrjo9XYcebt9fb0PvR+9r7ip4ZGuK7300kttK16dJ9W1pbr0B6hHBCoSRdemPv7442bvvfe216wmrZN9hZdq0Wq5u9OPHtyitW6c1GpYr6/3ofej9xWnJ5980vZ49Pzzz9uGR67HI1rxop4RqEicffbZx/zpT39KXCf7Y8eOteHVaYdm07s9zLbpV92amF5f70M1Vb0vvb9KU8Ojiy66yJxxxhm2Fa8aHqkfXlrxAgQqEsr1ppSUTvb1XnR4tbE9vHqNnFrSpTCVoPehmqrel97fpEmTgiXRU09Hanh077330vAIyIJARaIloZN99Xik60yl1/enVr1mGqb3o/clanms9xslHW6/6aabzHHHHWfmzZtnGx499thj9lpTug8EvkCgIvFcJ/tq/KKaketkf/78+cEalaXuEqX7IS1VO2faEb0vvT9x7zcKixcvtg2P1FhMh99/+MMf0vAIyIFARSqoE/mzzz7b3sB8wIAB5o033jBHHnmkvYa1knRdpc5PNu7QbDtsSLLtDxht36fer+tcIRd1k9hRy+BwwyP1y3vttdfS8AjIoVEbKiAthgwZYvuHPfHEE+3NqXXnkvPOO8+sWbMmWCM6ChwdQhV1rJB0Op/q3qfed77A1LlWBW82+ixdwyPdHUfXA6vh0VFHHRWsASAbaqhIHdWQpkyZYu9coptUq2GMaqsvvfRSsEY01MhHgaLeiZJ6qDdM71PvV+9b7z8bNS564IEHsgaqlqnxl9/wSB010PAI6BiBitQ66aSTbG118ODB5r333rPTqnmpj+AoKHQk7o4bytXta6faoXv/YZdffrkdunuzij4z1/Do/fffN3vuuWem4RFHsYDCEKhItYEDB9rzqrpmVR3s61CnglV3symHamqqwekaT3WikCbqntBdm6p/h08tgGfOnJkZF+2M6BC63/BI93Gl4RFQHAIVqdelS5ctrlmNopN9d7i021c31/bSxr3v8GFf/zpV9QOsRl36rF5++WXTu3fvTMOjavUNDKQZgYqa4a5ZVecDapCjO7JcfPHFtneffLJdt+nOL3b9crpqp4573/55Uu1gqHbqunFUoKpRlxp30fAIKB+Bipqia1azdbI/Z86cYI0t6ZCoa8nrc4dFu/yPfe0wbdz7/sc//mGHolq840JVDY90o3c1PFLtHkDpCFTUpHAn+8cee6y56667gqVfUC3thRde2KKWqms0Rdd0JqWLwWLpfes8qhoe6d8zbdo009raaoPUNTLSuM6ZqlP7lpaWzL8bQGkIVNQs18n+aaedZg/76hIQ3XdVXRg67pCoX0t1waL7j6ZZl76ba6n69/jnTv1QdXSudfjw4baDfYIVKA2Bipqmw76//e1vbV+8O+ywg/nLX/5ie//R5TbiWsGqlqpanBuXbVJy7Wku7v1rZ0G1U1GQujANh6oCVWGrc63VuL8qkHYNU5+a3bZi4dtm7I++F8wCapMupdH5QrUCFl0e8sorr5i33nrLTu+6667mxRdftLU5hZD6xk16d4P5fPL0JFu0U6EbgEtzc7Pp37+/Oeigg2x3gvvuu68t2tkAUB5qqKgbTU1N5uGHHzbnnnuunVZvQC5MVTPT+VRXS60lavWs60pVS1VvUrpUZty4cWbMmDE2WAlTIBoEKurOJZdcYm8Bp+tXRWHqZGvxm1ab1q60h3X/9V//lU4agBgQqKgras178skn20tIdE9VF6YKHldLddetrp8f7X1F47bhg80NrnRIF0DlEaioC2q5+uMf/9iccsopmUZHjgtTR33g+tMAUAgCFXVBNVPV1NSSVQ1zHL/Fqxv/8MMP7fiGFQvtdFq5969GSAAqj1a+qFu6ZEaHeF0n8hp3PQu5Gmrf8f+dys4ddP70g2u/YsfdJTMAKosaKuqWGuqMGDHCtnhVp/C6NlXhoxax6hRC1r+35eHhtFg3Z/ONAVQjBxAPAhUIUdD+4Ac/sId9171V+h1rqmn9/M07AtphABAPAhXIwgXRZ3Om22HarAveN4EKxIdABbJQQx41Xtq0blXqaql6v23t7/srX/kKDZKAGBGoQA4jR460wzUzb7PDtHDvl9opEC8CFchh9OjRtpaqhkmf/j0dXRLqfer96n3r/QOID4EK5KA+btUCWD55Oh1dErr3qfdNH71AvAhUIA8d9tW5yE0rF9o7tySZ3p/ep96vO1wNID4EKtCBK664wg5XPzM5sQ2UdKhX70/c+wUQLwIV6IBucTZhwgQ7vvKRsWb94s03JU8KvZ9Ppm9+f3qfer8A4kegAgXQvUPVsb4uo/no/7UP164MllSX3od9P+3vS+9P7xNAdRCoQIFuuOEG25WfrvFUiFW7pqrX1/vQ+9H70vsDUD0EKlCEqVOn2kY/ny9503zcHmbVOqeq19Xr633o/eh9AaguAhUogi5FUSf67vDvx9PONGtejLfjB72eXtcd5tX74RIZoPoIVKAEOrw6efJk071HD7PqicvN8jtPNp/N/2uwtDL0/HodvZ5eV6/PYV4gOQhUoES61vMPDz6Y6U3po7tOMSseHms2rlgQrBENPZ+eV8/vekHS63KtKZAsBCpQBt3qzR0ClrWv3W+W/u/hNgA//fv9JbcG1uP0eD2Pnk/PK+4Qr14XQLI0TH1qdtuKhW+bsT/6XjALQClWrlxpbrvtNvP7+6aZxYtag7nGdOm7r+k6aITp3D5s2LannbftwAPtUD4L7l3a9tkqs2HJm7bBkRobOf2ams2o74+0ffNyrhRILgIVqIBp06aZ+++/38ycOTOYUzxdCnPqqadyaBdICQIVAICyGfP/AQCGqhh2lg9MAAAAAElFTkSuQmCC" } }, "cell_type": "markdown", "metadata": {}, "source": [ "## OpenMP reduction\n", "\n", "The reduction clauses are data-sharing attribute clauses that can be used to perform some forms of recurrence calculations in parallel.\n", "\n", "### Example - Array Addition with OpenMP parallel programming\n", "\n", "Let's now try to understand how to parallelize a simple for loop using OpenMP. For example, we want to sum-up all the numbers from 1-12, but using 3 threads in parallel. Let's observe the following figure\n", "\n", "![image_s01.png](attachment:f2183b4a-a55e-4338-ab61-8c10f015419d.png)\n", "\n", "The code will be something like this:\n", "\n", "```\n", "#include \n", "#include \n", "#include \n", "\n", "int main(){\n", " double sum_i = 0;\n", " #pragma omp parallel for reduction(+:sum_i)\n", " for (int i=0; i<12; i++){\n", " sum_i += i;\n", " \n", " }\n", " std::cout << \"Sum = \" << sum_i << std::endl;\n", " return 0;\n", "}\n", "```\n", "\n", "And we will compile it and run it. The previous code was C, but this is C++, so we will use the `g++` compiler, the sintax is very similar as you can see. We will pass again the option `-fopenmp` to the compiler. To tell that it should use as many threads as available cores.\n" ] }, { "cell_type": "code", "execution_count": 6, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C++ program written to array_addition.cpp.\n", "Compiling the C++ program...\n", "Compilation successful, executable created.\n", "Running the C++ program...\n", "Program Output:\n", " Thread 0 adding 1, partial sum: 1.000000\n", "Thread 0 adding 2, partial sum: 3.000000\n", "Thread 0 adding 3, partial sum: 6.000000\n", "Thread 3 adding 10, partial sum: 10.000000\n", "Thread 3 adding 11, partial sum: 21.000000\n", "Thread 3 adding 12, partial sum: 33.000000\n", "Thread 2 adding 7, partial sum: 7.000000\n", "Thread 2 adding 8, partial sum: 15.000000\n", "Thread 2 adding 9, partial sum: 24.000000\n", "Thread 1 adding 4, partial sum: 4.000000\n", "Thread 1 adding 5, partial sum: 9.000000\n", "Thread 1 adding 6, partial sum: 15.000000\n", "Final Sum = 78\n", "\n" ] } ], "source": [ "import os\n", "import subprocess\n", "\n", "# Define the path for the C++ program file\n", "cpp_program_path = \"array_addition.cpp\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(cpp_program_path):\n", " os.remove(cpp_program_path)\n", "\n", "# Create and write the C++ program\n", "cpp_program = \"\"\"\n", "#include \n", "#include \n", "\n", "int main() {\n", " double sum_i = 0;\n", " #pragma omp parallel for reduction(+:sum_i)\n", " for (int i = 1; i <= 12; i++) {\n", " sum_i += i;\n", " int thread_id = omp_get_thread_num();\n", " printf(\"Thread %d adding %d, partial sum: %f\\\\n\", thread_id, i, sum_i);\n", " }\n", " std::cout << \"Final Sum = \" << sum_i << std::endl;\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C++ program to a file\n", "with open(cpp_program_path, \"w\") as file:\n", " file.write(cpp_program)\n", "\n", "print(f\"C++ program written to {cpp_program_path}.\")\n", "\n", "# Compile the C++ program using g++ with OpenMP support\n", "compile_command = f\"g++ -o array_addition -fopenmp {cpp_program_path}\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C++ program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "executable_path = \"array_addition\"\n", "if os.path.exists(executable_path):\n", " print(\"Compilation successful, executable created.\")\n", "else:\n", " print(\"Compilation failed.\")\n", "\n", "# Run the compiled program\n", "run_command = f\"./{executable_path}\"\n", "run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output of the program execution\n", "print(\"Running the C++ program...\")\n", "if run_process.stdout:\n", " print(\"Program Output:\\n\", run_process.stdout)\n", "if run_process.stderr:\n", " print(\"Program Error:\\n\", run_process.stderr)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Array Addition with OpenMP\n", "\n", "In this C++ program, we utilize the `#pragma omp parallel for reduction(+:sum_i)` directive to parallelize the summation of numbers from 1 to 12.\n", "\n", "- **Parallelization:** The loop that sums up the numbers is parallelized using OpenMP. The `reduction(+:sum_i)` clause ensures that each thread computes its partial sum independently and then combines these partial sums into a final result.\n", "\n", "- **Thread Execution:** Each thread is responsible for adding a subset of the numbers. The program prints which thread is processing which number and shows the partial sum being calculated.\n", "\n", "- **Output:** After the loop completes, the program outputs the final sum, which should be the sum of numbers from 1 to 12.\n", "\n", "By using multiple threads, the program demonstrates how OpenMP can efficiently parallelize operations that involve accumulation, reducing the overall computation time in more complex scenarios.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "You can run it direclty:\n", "\n", "```\n", "cd ./openmp\n", "g++ -o array_addition array_addition.cpp -fopenmp\n", "./array_addition\n", "```\n", "\n", "You can modify the C++ source code of the program and see the result after compiling it. \n", "\n", "For example, would you like to see the thread id of each thread, what would you change?\n", "\n", " int tid;\n", " #pragma omp parallel for reduction(+:sum_i)\n", " for (int i=0; i<12; i++){\n", " sum_i += i;\n", " tid = omp_get_thread_num();\n", " printf(\"threadid = %d\\n\", tid); \n", " \n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OpenMP Sections\n", "\n", "The `omp sections` directive in OpenMP allows different code blocks to be executed in parallel by separate threads. This is particularly useful when you have multiple independent tasks that can be run concurrently, each performing a different operation.\n", "\n", "### Example: Parallel Tasks with OpenMP Sections\n", "\n", "In this example, we will create a C++ program where different sections of code (each performing a distinct task) are executed in parallel using OpenMP. Each section will perform a specific calculation and print which thread is executing it.\n" ] }, { "cell_type": "code", "execution_count": 7, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C++ program written to omp_sections_example.cpp.\n", "Compiling the C++ program...\n", "Compilation successful, executable created.\n", "Running the C++ program...\n", "Program Output:\n", " Task 1 is being executed by thread 0\n", "Task 2 is being executed by thread 0\n", "Task 3 is being executed by thread 0\n", "\n" ] } ], "source": [ "import os\n", "import subprocess\n", "\n", "# Define the path for the C++ program file\n", "cpp_program_path = \"omp_sections_example.cpp\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(cpp_program_path):\n", " os.remove(cpp_program_path)\n", "\n", "# Create and write the C++ program\n", "cpp_program = \"\"\"\n", "#include \n", "#include \n", "\n", "void task1() {\n", " printf(\"Task 1 is being executed by thread %d\\\\n\", omp_get_thread_num());\n", "}\n", "\n", "void task2() {\n", " printf(\"Task 2 is being executed by thread %d\\\\n\", omp_get_thread_num());\n", "}\n", "\n", "void task3() {\n", " printf(\"Task 3 is being executed by thread %d\\\\n\", omp_get_thread_num());\n", "}\n", "\n", "int main() {\n", " #pragma omp parallel sections\n", " {\n", " #pragma omp section\n", " {\n", " task1();\n", " }\n", "\n", " #pragma omp section\n", " {\n", " task2();\n", " }\n", "\n", " #pragma omp section\n", " {\n", " task3();\n", " }\n", " }\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C++ program to a file\n", "with open(cpp_program_path, \"w\") as file:\n", " file.write(cpp_program)\n", "\n", "print(f\"C++ program written to {cpp_program_path}.\")\n", "\n", "# Compile the C++ program using g++ with OpenMP support\n", "compile_command = f\"g++ -o omp_sections_example -fopenmp {cpp_program_path}\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C++ program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "executable_path = \"omp_sections_example\"\n", "if os.path.exists(executable_path):\n", " print(\"Compilation successful, executable created.\")\n", "else:\n", " print(\"Compilation failed.\")\n", "\n", "# Run the compiled program\n", "run_command = f\"./{executable_path}\"\n", "run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output of the program execution\n", "print(\"Running the C++ program...\")\n", "if run_process.stdout:\n", " print(\"Program Output:\\n\", run_process.stdout)\n", "if run_process.stderr:\n", " print(\"Program Error:\\n\", run_process.stderr)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### Parallel Tasks with OpenMP Sections\n", "\n", "In this C++ program, we use the `#pragma omp parallel sections` directive to run different tasks concurrently. Each section in the program is executed by a different thread.\n", "\n", "- **Sections Directive:** The `#pragma omp sections` directive tells OpenMP to execute the enclosed code blocks in parallel. Each `#pragma omp section` defines a block of code that will run in a separate thread.\n", "\n", "- **Tasks:** The program defines three tasks (`task1`, `task2`, and `task3`), each of which prints the thread number that is executing it. This helps in understanding how different sections of the code are handled by different threads.\n", "\n", "- **Parallel Execution:** When the program is run, you will see that the tasks are executed in parallel by different threads. The output will show which thread is handling each task.\n", "\n", "### Benefits of Using OpenMP Sections\n", "\n", "Using `omp sections` is beneficial when you have multiple independent tasks that can be executed simultaneously. This approach can significantly reduce the overall execution time in scenarios where tasks are computationally intensive but independent of each other.\n", "\n", "By running the example, you will observe the parallel execution of different tasks, demonstrating the power and flexibility of OpenMP for parallel programming.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## OpenMP Barriers\n", "\n", "The `omp barrier` directive in OpenMP is used to synchronize threads. When a barrier is encountered, all threads in a team must reach the barrier before any can proceed. This ensures that certain sections of the code are executed by all threads up to a certain point before moving forward.\n", "\n", "### Example: Synchronization with OpenMP Barriers\n", "\n", "In this example, we will create a C++ program where multiple threads perform some tasks in parallel, but they need to synchronize at certain points to ensure the correctness of the program. The `omp barrier` directive will be used to synchronize the threads.\n" ] }, { "cell_type": "code", "execution_count": 8, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C++ program written to omp_barrier_example.cpp.\n", "Compiling the C++ program...\n", "Compilation successful, executable created.\n", "Running the C++ program...\n", "Program Output:\n", " Thread 0: Performing initial task...\n", "Thread 3: Performing initial task...\n", "Thread 2: Performing initial task...\n", "Thread 1: Performing initial task...\n", "Thread 0: Performing task after barrier...\n", "Thread 3: Performing task after barrier...\n", "Thread 2: Performing task after barrier...\n", "Thread 1: Performing task after barrier...\n", "Thread 0: Performing final task...\n", "Thread 3: Performing final task...\n", "Thread 2: Performing final task...\n", "Thread 1: Performing final task...\n", "Total number of threads used: 4\n", "\n" ] } ], "source": [ "import os\n", "import subprocess\n", "\n", "# Define the path for the C++ program file\n", "cpp_program_path = \"omp_barrier_example.cpp\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(cpp_program_path):\n", " os.remove(cpp_program_path)\n", "\n", "# Create and write the C++ program\n", "cpp_program = \"\"\"\n", "#include \n", "#include \n", "\n", "int main() {\n", " int num_threads = 0;\n", "\n", " #pragma omp parallel\n", " {\n", " int thread_id = omp_get_thread_num();\n", " \n", " // Each thread performs this task\n", " printf(\"Thread %d: Performing initial task...\\\\n\", thread_id);\n", " \n", " // Synchronize threads at this point\n", " #pragma omp barrier\n", " \n", " // Only after all threads reach this barrier, they perform the next task\n", " printf(\"Thread %d: Performing task after barrier...\\\\n\", thread_id);\n", " \n", " // Synchronize threads again\n", " #pragma omp barrier\n", " \n", " // Final task after the second barrier\n", " printf(\"Thread %d: Performing final task...\\\\n\", thread_id);\n", "\n", " // Update the number of threads used (only by one thread to avoid race conditions)\n", " #pragma omp single\n", " {\n", " num_threads = omp_get_num_threads();\n", " }\n", " }\n", " \n", " printf(\"Total number of threads used: %d\\\\n\", num_threads);\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C++ program to a file\n", "with open(cpp_program_path, \"w\") as file:\n", " file.write(cpp_program)\n", "\n", "print(f\"C++ program written to {cpp_program_path}.\")\n", "\n", "# Compile the C++ program using g++ with OpenMP support\n", "compile_command = f\"g++ -o omp_barrier_example -fopenmp {cpp_program_path}\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C++ program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "executable_path = \"omp_barrier_example\"\n", "if os.path.exists(executable_path):\n", " print(\"Compilation successful, executable created.\")\n", "else:\n", " print(\"Compilation failed.\")\n", "\n", "# Run the compiled program\n", "run_command = f\"./{executable_path}\"\n", "run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output of the program execution\n", "print(\"Running the C++ program...\")\n", "if run_process.stdout:\n", " print(\"Program Output:\\n\", run_process.stdout)\n", "if run_process.stderr:\n", " print(\"Program Error:\\n\", run_process.stderr)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "\n", "### Synchronization with OpenMP Barriers\n", "\n", "In this C++ program, we use the `#pragma omp barrier` directive to synchronize threads at specific points in the code.\n", "\n", "- **Parallel Region:** The `#pragma omp parallel` directive creates a team of threads. Each thread executes the code within the parallel region.\n", "\n", "- **Initial Task:** Each thread performs an initial task, such as printing a message indicating its thread ID.\n", "\n", "- **First Barrier:** After the initial task, we use `#pragma omp barrier` to ensure that all threads reach this point before any thread can proceed to the next section of the code. This synchronization is crucial in scenarios where subsequent tasks depend on the completion of previous tasks by all threads.\n", "\n", "- **Second Task:** Once all threads have reached the first barrier, they proceed to the next task, which is again synchronized using a barrier.\n", "\n", "- **Final Task:** After the second barrier, the threads perform their final tasks.\n", "\n", "- **Single Directive:** The `#pragma omp single` directive ensures that only one thread updates the `num_threads` variable to avoid race conditions. This demonstrates how you can control access to shared resources in parallel regions.\n", "\n", "### Benefits of Using OpenMP Barriers\n", "\n", "The `omp barrier` directive is essential when you need to ensure that all threads have completed a certain portion of the code before moving forward. This is common in parallel algorithms where steps are dependent on the completion of previous steps by all threads.\n", "\n", "By running the example, you will observe how threads synchronize their execution using barriers, which is a key aspect of ensuring correctness in parallel programs.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Image Processing with OpenMP\n", "\n", "Image processing is a computationally intensive task that can benefit significantly from parallelization. Convolution operations, which apply a filter or kernel to an image, are particularly well-suited for parallel execution due to their repetitive nature and localized data dependencies.\n", "\n", "In this example, we focus on parallelizing convolution operations using OpenMP to improve performance. Convolution is commonly used for tasks like edge detection, blurring, and sharpening in digital images.\n", "\n", "By using the `#pragma omp parallel for` directive with `collapse(2)`, the nested loops for iterating over the image are collapsed into a single parallel loop. This allows the workload to be distributed evenly across multiple threads, resulting in significant speedup, especially on systems with many cores. Performance improvements can be measured by comparing execution time with and without parallelization, using a tool like Intel VTune or GNU time.\n" ] }, { "cell_type": "code", "execution_count": 9, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C program written to image_processing_openmp.c.\n", "Compiling the C program...\n", "Compilation successful, executable created.\n", "Running the C program...\n", "Program Output:\n", " Image Section:\n", " 70.0 100.0 49.0 41.0 100.0 \n", " 107.0 203.0 54.0 235.0 114.0 \n", " 29.0 78.0 69.0 144.0 87.0 \n", " 103.0 218.0 134.0 19.0 236.0 \n", " 26.0 130.0 172.0 70.0 32.0 \n", "Output Section:\n", " 0.0 0.0 0.0 0.0 0.0 \n", " 0.0 473.0 -340.0 587.0 -3.0 \n", " 0.0 -207.0 -134.0 166.0 -230.0 \n", " 0.0 427.0 58.0 -508.0 690.0 \n", " 0.0 83.0 344.0 -145.0 -402.0 \n", "Output Section:\n", " 0.0 0.0 0.0 0.0 0.0 \n", " 0.0 473.0 -340.0 587.0 -3.0 \n", " 0.0 -207.0 -134.0 166.0 -230.0 \n", " 0.0 427.0 58.0 -508.0 690.0 \n", " 0.0 83.0 344.0 -145.0 -402.0 \n", "Parallel Execution Time: 0.087769 seconds\n", "Serial Execution Time: 0.086834 seconds\n", "\n" ] } ], "source": [ "import os\n", "import subprocess\n", "import time\n", "\n", "# Define the path for the C program file\n", "c_program_path = \"image_processing_openmp.c\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(c_program_path):\n", " os.remove(c_program_path)\n", "\n", "# Create and write the C program\n", "c_program = \"\"\"\n", "#include \n", "#include \n", "#include \n", "#include \n", "\n", "#define WIDTH 1920\n", "#define HEIGHT 1080\n", "#define KERNEL_SIZE 3\n", "\n", "void apply_convolution(double **image, double **output, double kernel[KERNEL_SIZE][KERNEL_SIZE]) {\n", " #pragma omp parallel for collapse(2)\n", " for (int y = 1; y < HEIGHT - 1; y++) {\n", " for (int x = 1; x < WIDTH - 1; x++) {\n", " double sum = 0.0;\n", " for (int ky = 0; ky < KERNEL_SIZE; ky++) {\n", " for (int kx = 0; kx < KERNEL_SIZE; kx++) {\n", " int ix = x + kx - 1;\n", " int iy = y + ky - 1;\n", " sum += image[iy][ix] * kernel[ky][kx];\n", " }\n", " }\n", " output[y][x] = sum;\n", " }\n", " }\n", "}\n", "\n", "void apply_convolution_serial(double **image, double **output, double kernel[KERNEL_SIZE][KERNEL_SIZE]) {\n", " for (int y = 1; y < HEIGHT - 1; y++) {\n", " for (int x = 1; x < WIDTH - 1; x++) {\n", " double sum = 0.0;\n", " for (int ky = 0; ky < KERNEL_SIZE; ky++) {\n", " for (int kx = 0; kx < KERNEL_SIZE; kx++) {\n", " int ix = x + kx - 1;\n", " int iy = y + ky - 1;\n", " sum += image[iy][ix] * kernel[ky][kx];\n", " }\n", " }\n", " output[y][x] = sum;\n", " }\n", " }\n", "}\n", "\n", "void print_image_section(double **image, int start_x, int start_y, int size) {\n", " printf(\"Image Section:\\\\n\");\n", " for (int y = start_y; y < start_y + size; y++) {\n", " for (int x = start_x; x < start_x + size; x++) {\n", " printf(\"%6.1f \", image[y][x]);\n", " }\n", " printf(\"\\\\n\");\n", " }\n", "}\n", "\n", "void print_output_section(double **output, int start_x, int start_y, int size) {\n", " printf(\"Output Section:\\\\n\");\n", " for (int y = start_y; y < start_y + size; y++) {\n", " for (int x = start_x; x < start_x + size; x++) {\n", " printf(\"%6.1f \", output[y][x]);\n", " }\n", " printf(\"\\\\n\");\n", " }\n", "}\n", "\n", "int main() {\n", " // Dynamically allocate memory for images\n", " double **image = malloc(HEIGHT * sizeof(double *));\n", " double **output_parallel = malloc(HEIGHT * sizeof(double *));\n", " double **output_serial = malloc(HEIGHT * sizeof(double *));\n", " for (int i = 0; i < HEIGHT; i++) {\n", " image[i] = malloc(WIDTH * sizeof(double));\n", " output_parallel[i] = malloc(WIDTH * sizeof(double));\n", " output_serial[i] = malloc(WIDTH * sizeof(double));\n", " }\n", "\n", " double kernel[KERNEL_SIZE][KERNEL_SIZE] = {\n", " {0, -1, 0},\n", " {-1, 4, -1},\n", " {0, -1, 0}\n", " };\n", "\n", " // Seed the random number generator for reproducibility\n", " srand(42);\n", "\n", " // Initialize image with random values\n", " for (int y = 0; y < HEIGHT; y++) {\n", " for (int x = 0; x < WIDTH; x++) {\n", " image[y][x] = rand() % 256;\n", " }\n", " }\n", "\n", " // Apply parallel convolution\n", " double start_time_parallel = omp_get_wtime();\n", " apply_convolution(image, output_parallel, kernel);\n", " double end_time_parallel = omp_get_wtime();\n", "\n", " // Apply serial convolution\n", " double start_time_serial = omp_get_wtime();\n", " apply_convolution_serial(image, output_serial, kernel);\n", " double end_time_serial = omp_get_wtime();\n", "\n", " // Print a 5x5 section of the image and output for representation\n", " print_image_section(image, 0, 0, 5);\n", " print_output_section(output_parallel, 0, 0, 5);\n", " print_output_section(output_serial, 0, 0, 5);\n", "\n", " // Compare and print the execution times\n", " printf(\"Parallel Execution Time: %f seconds\\\\n\", end_time_parallel - start_time_parallel);\n", " printf(\"Serial Execution Time: %f seconds\\\\n\", end_time_serial - start_time_serial);\n", "\n", " // Free dynamically allocated memory\n", " for (int i = 0; i < HEIGHT; i++) {\n", " free(image[i]);\n", " free(output_parallel[i]);\n", " free(output_serial[i]);\n", " }\n", " free(image);\n", " free(output_parallel);\n", " free(output_serial);\n", "\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C program to a file\n", "with open(c_program_path, \"w\") as file:\n", " file.write(c_program)\n", "\n", "print(f\"C program written to {c_program_path}.\")\n", "\n", "# Compile the C program using gcc with OpenMP support\n", "compile_command = f\"gcc -o image_processing_openmp -fopenmp {c_program_path}\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "executable_path = \"image_processing_openmp\"\n", "if os.path.exists(executable_path):\n", " print(\"Compilation successful, executable created.\")\n", "else:\n", " print(\"Compilation failed.\")\n", "\n", "# Run the compiled program\n", "run_command = f\"./{executable_path}\"\n", "run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output of the program execution\n", "print(\"Running the C program...\")\n", "if run_process.stdout:\n", " print(\"Program Output:\\n\", run_process.stdout)\n", "if run_process.stderr:\n", " print(\"Program Error:\\n\", run_process.stderr)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "0. **Writing and Compiling**:\n", " - The C program is written to a file named `image_processing_openmp.c`.\n", " - It is then compiled using the `gcc` compiler with OpenMP support enabled (`-fopenmp`).\n", "\n", "1. **Parallelizing Convolution**:\n", " - The convolution operation is parallelized using OpenMP. The `#pragma omp parallel for collapse(2)` directive is used to parallelize the nested loops. This allows for efficient utilization of multiple CPU cores by distributing the work of applying the kernel across multiple threads.\n", "\n", "2. **Memory Allocation**:\n", " - The image and output arrays are dynamically allocated to handle large image sizes typical in high-resolution images (e.g., 1920x1080). This ensures the program can handle varying image sizes without hardcoding limits.\n", "\n", "3. **Random Image Initialization**:\n", " - For demonstration purposes, the image is filled with random values. This simulates a real-world scenario where image data would be processed.\n", "\n", "4. **Kernel Definition**:\n", " - A simple 3x3 kernel is used in this example for edge detection. The kernel values can be modified to apply different filters (e.g., blurring, sharpening).\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "# Financial Analytics with OpenMP\n", "\n", "Financial analytics often involve complex simulations that require significant computational power. Monte Carlo simulations, which are used to model the probability of different outcomes in financial markets, are a prime example. These simulations rely on repeated random sampling to calculate results, making them highly parallelizable.\n", "\n", "In this notebook, we demonstrate how OpenMP can be used to parallelize Monte Carlo simulations, improving efficiency and enabling faster data analysis. By leveraging multiple threads, we can significantly reduce the time taken to perform large-scale simulations.\n" ] }, { "cell_type": "code", "execution_count": 12, "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "C program written to monte_carlo_openmp.c.\n", "Compiling the C program...\n", "Compilation successful, executable created.\n", "Running the C program...\n", "Program Output:\n", " Threads: 1, Estimated Option Price: 10.462102, Execution Time: 1.159452 seconds\n", "Threads: 2, Estimated Option Price: 10.462223, Execution Time: 1.168060 seconds\n", "Threads: 3, Estimated Option Price: 10.462024, Execution Time: 1.167078 seconds\n", "Threads: 4, Estimated Option Price: 10.462104, Execution Time: 1.174924 seconds\n", "Threads: 5, Estimated Option Price: 10.462031, Execution Time: 1.168560 seconds\n", "Threads: 6, Estimated Option Price: 10.462172, Execution Time: 1.172370 seconds\n", "Threads: 7, Estimated Option Price: 10.462162, Execution Time: 1.168552 seconds\n", "Threads: 8, Estimated Option Price: 10.461900, Execution Time: 1.171045 seconds\n", "\n" ] } ], "source": [ "import os\n", "import subprocess\n", "\n", "# Define the path for the C program file\n", "c_program_path = \"monte_carlo_openmp.c\"\n", "\n", "# Remove the existing file if it exists\n", "if os.path.exists(c_program_path):\n", " os.remove(c_program_path)\n", "\n", "# Create and write the C program\n", "c_program = \"\"\"\n", "#include \n", "#include \n", "#include \n", "#include \n", "\n", "#define NUM_SIMULATIONS 1000000 // Number of Monte Carlo simulations\n", "#define MAX_THREADS 8 // Maximum number of OpenMP threads\n", "\n", "// Function to generate a normally distributed random number using Box-Muller transform\n", "double rand_normal() {\n", " double u = (double)rand() / RAND_MAX;\n", " double v = (double)rand() / RAND_MAX;\n", " return sqrt(-2.0 * log(u)) * cos(2.0 * M_PI * v);\n", "}\n", "\n", "// Monte Carlo simulation for European call option pricing\n", "double monte_carlo_option_pricing(int seed, double S, double K, double r, double sigma, double T) {\n", " srand(seed);\n", " double z = rand_normal();\n", " double S_T = S * exp((r - 0.5 * sigma * sigma) * T + sigma * sqrt(T) * z); // Simulate final stock price\n", " double payoff = fmax(0.0, S_T - K); // Payoff of the European call option\n", " return payoff;\n", "}\n", "\n", "int main() {\n", " double S = 100.0; // Initial stock price\n", " double K = 100.0; // Strike price\n", " double r = 0.05; // Risk-free interest rate\n", " double sigma = 0.2; // Volatility\n", " double T = 1.0; // Time to maturity (1 year)\n", "\n", " for (int num_threads = 1; num_threads <= MAX_THREADS; num_threads++) {\n", " double sum = 0.0;\n", " double start_time = omp_get_wtime();\n", "\n", " #pragma omp parallel for num_threads(num_threads) reduction(+:sum)\n", " for (int i = 0; i < NUM_SIMULATIONS; i++) {\n", " double payoff = monte_carlo_option_pricing(i, S, K, r, sigma, T);\n", " sum += payoff;\n", " }\n", "\n", " double option_price = (sum / NUM_SIMULATIONS) * exp(-r * T); // Discounted expected payoff\n", " double end_time = omp_get_wtime();\n", "\n", " printf(\"Threads: %d, Estimated Option Price: %f, Execution Time: %f seconds\\\\n\", num_threads, option_price, end_time - start_time);\n", " }\n", "\n", " return 0;\n", "}\n", "\"\"\"\n", "\n", "# Write the C program to a file\n", "with open(c_program_path, \"w\") as file:\n", " file.write(c_program)\n", "\n", "print(f\"C program written to {c_program_path}.\")\n", "\n", "# Compile the C program using gcc with OpenMP and math library support\n", "compile_command = f\"gcc -o monte_carlo_openmp -fopenmp {c_program_path} -lm\"\n", "compile_process = subprocess.run(compile_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output and error (if any) after compilation attempt\n", "print(\"Compiling the C program...\")\n", "if compile_process.stdout:\n", " print(\"Output:\", compile_process.stdout)\n", "if compile_process.stderr:\n", " print(\"Error:\", compile_process.stderr)\n", "\n", "# Check if the executable was created\n", "executable_path = \"monte_carlo_openmp\"\n", "if os.path.exists(executable_path):\n", " print(\"Compilation successful, executable created.\")\n", "else:\n", " print(\"Compilation failed.\")\n", "\n", "# Run the compiled program\n", "run_command = f\"./{executable_path}\"\n", "run_process = subprocess.run(run_command, shell=True, capture_output=True, text=True)\n", "\n", "# Print the output of the program execution\n", "print(\"Running the C program...\")\n", "if run_process.stdout:\n", " print(\"Program Output:\\n\", run_process.stdout)\n", "if run_process.stderr:\n", " print(\"Program Error:\\n\", run_process.stderr)\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Monte Carlo Simulation for Option Pricing with OpenMP\n", "\n", "In this program, we use Monte Carlo simulations to estimate the price of a European call option, a common financial derivative. The option price is determined by simulating random stock price paths and calculating the option's payoff based on those simulations. The simulation is parallelized using OpenMP to speed up computation.\n", "\n", "#### Key Components:\n", "\n", "- **Monte Carlo Simulation for Option Pricing:**\n", " - The program simulates the evolution of a stock's price using a stochastic model (the Black-Scholes model), where the stock price at maturity (`S_T`) is influenced by random factors. The payoff of the option is calculated as `max(0, S_T - K)`, where `K` is the strike price.\n", " - The expected payoff from multiple simulations is then discounted back to the present value using the risk-free interest rate to estimate the option price.\n", "\n", "- **Parallelization with OpenMP:**\n", " - The program is parallelized using the `#pragma omp parallel for` directive. This allows the simulations to run concurrently on multiple threads. The `reduction(+:sum)` clause ensures that the payoffs computed by each thread are safely accumulated into the `sum` variable.\n", " - The program scales from 1 to 8 threads, allowing you to observe the performance gains from parallel execution.\n", "\n", "- **Thread Scaling and Performance:**\n", " - The program runs the simulation with varying numbers of threads (from 1 to 8) to demonstrate how parallelization affects execution time. By comparing the execution time for different thread counts, we can measure the impact of parallel computing on the performance of large-scale simulations.\n", " - The more threads that are used, the faster the program can complete the simulations, as the workload is distributed across the available CPU cores.\n", "\n", "- **Time Measurement:**\n", " - The execution time for each configuration (1 to 8 threads) is measured using `omp_get_wtime()`. This helps demonstrate how efficiently the workload is distributed across threads and the resulting reduction in computation time.\n", "\n", "#### Output:\n", "- For each number of threads, the program prints:\n", " - **Estimated Option Price**: The calculated option price based on the Monte Carlo simulation.\n", " - **Execution Time**: The time taken to complete the simulation with the given number of threads.\n", "\n", "By running this program, you can see how using multiple threads with OpenMP speeds up the Monte Carlo simulation and how it impacts the overall time to estimate the option price. This illustrates the power of parallel computing in financial analytics, where quick computations are crucial for making timely decisions.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "### Understanding How OpenMP Works on Individual Nodes\n", "\n", "OpenMP (Open Multi-Processing) is a parallel programming model designed for shared memory architectures. It allows you to parallelize tasks across multiple threads on a single node (machine), making it ideal for multi-core processors, such as those found in most modern laptops and desktops.\n", "\n", "#### Key Concepts:\n", "- **Shared Memory Parallelism**: OpenMP operates within a shared memory space, meaning all threads in the program can access the same memory. This makes OpenMP a great tool for parallelizing tasks within a single node, such as your personal laptop or a single server.\n", " \n", "- **Multi-Core Utilization**: Modern laptops and desktops typically have multiple cores (e.g., 4, 8, or more). OpenMP can take advantage of these cores to run multiple threads in parallel, speeding up computations that would otherwise run sequentially.\n", "\n", "#### How OpenMP Works on Your Laptop:\n", "When you run an OpenMP program on your laptop, the program will create multiple threads that execute concurrently across the available CPU cores. For example, if your laptop has 4 cores, you can instruct OpenMP to run 4 threads, one per core, to divide the workload and perform tasks simultaneously. OpenMP is built into most C/C++ and Fortran compilers (e.g., GCC), making it easy to set up and use on local machines.\n", "\n", "#### Getting Started with OpenMP on Your Laptop:\n", "1. **Installing a Compiler with OpenMP Support**:\n", " - OpenMP is supported by many compilers, such as GCC, which is available on Linux, macOS, and Windows (via MinGW or WSL).\n", " - To install GCC:\n", " - On **Linux**: Run `sudo apt-get install gcc` (for Ubuntu) or the equivalent package manager command.\n", " - On **macOS**: You can install GCC with Homebrew by running `brew install gcc`.\n", " - On **Windows**: Use MinGW or Windows Subsystem for Linux (WSL) and install GCC.\n", "\n", "2. **Compiling an OpenMP Program**:\n", " - To compile a C program that uses OpenMP, simply add the `-fopenmp` flag to the GCC compiler command:\n", " ```bash\n", " gcc -fopenmp -o program_name program_name.c\n", " ```\n", " - This flag enables OpenMP support in the program and allows the code to run across multiple threads.\n", "\n", "3. **Running OpenMP Programs**:\n", " - Once compiled, you can run your OpenMP program on your laptop. By default, OpenMP will try to use all available cores, but you can control the number of threads by setting the environment variable `OMP_NUM_THREADS`:\n", " ```bash\n", " export OMP_NUM_THREADS=4 # Use 4 threads\n", " ./program_name\n", " ```\n", "\n", "#### Why Start with OpenMP on Your Laptop?\n", "OpenMP is a great way to get started with parallel programming because:\n", "- **Ease of Use**: It's simple to integrate OpenMP into existing C/C++ code with minimal modifications.\n", "- **Immediate Benefits**: Even on a small scale (like a laptop with 4-8 cores), you can observe performance improvements in computationally intensive tasks.\n", "- **Scalability**: Once you understand how OpenMP works on a laptop, you can easily scale your knowledge to more powerful systems like high-performance computing (HPC) clusters.\n", "\n", "By practicing on your laptop, you can gain hands-on experience with parallel programming and experiment with how OpenMP improves performance for various tasks, including scientific simulations, data processing, and more.\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "This is the end of the practice." ] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.9.6" }, "latex_envs": { "LaTeX_envs_menu_present": true, "autoclose": false, "autocomplete": true, "bibliofile": "biblio.bib", "cite_by": "apalike", "current_citInitial": 1, "eqLabelWithNumbers": true, "eqNumInitial": 1, "hotkeys": { "equation": "Ctrl-E", "itemize": "Ctrl-I" }, "labels_anchors": false, "latex_user_defs": false, "report_style_numbering": false, "user_envs_cfg": false } }, "nbformat": 4, "nbformat_minor": 4 }