course/1_fundamentals.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# **1 - OpenMP**\n",
    "\n",
    "OpenMP (Open Multi-Processing) is an application programming interface (API) that supports multi-platform shared-memory multiprocessing programming in C, C++, and Fortran. It consists of a set of compiler ```#pragmas``` that control how the program works. The pragmas are designed so that even if the compiler does not support them, the program will still yield correct behavior, but without any parallelism.\n",
    "\n",
    "\n",
    "## **1.1 - Execution Model**\n",
    "\n",
    "The OpenMP API uses the fork-join model of parallel execution. Multiple threads of execution perform tasks deﬁned implicitly or explicitly by OpenMP directives. The OpenMP API is intended to support programs that will execute correctly both as parallel programs (multiple threads of execution and a full OpenMP support library) and as sequential programs (directives ignored and a simple OpenMP stubs library). However, a conforming OpenMP program may execute correctly as a parallel program but not as a sequential program, or may produce diﬀerent results when executed as a parallel program compared to when it is executed as a sequential program. Further, using diﬀerent numbers of threads may result in diﬀerent numeric results because of changes in the association of numeric operations. For example, a serial addition reduction may have a diﬀerent pattern of addition associations than a parallel reduction. These diﬀerent associations may change the results of ﬂoating-point addition.\n",
    "\n",
    "An OpenMP program begins as a single thread of execution, called an initial thread (also known as Master thread), as depicted in Figure below. An initial thread executes sequentially until it reaches a parallel directive that tells the compiler to generate parallel code (fork). At this point, worker threads are created to execute the parallel region. At the end of a parallel region, there is an implicit synchronization to join all the threads (join). From this point on, only the master thread executes. This process repeats for every new parallel region in the code.\n",
    "\n",
    "<img src=\"../imgs/forkjoin.png\" alt=\"alt text\" width=\"700\" height=\"300\" class=\"blog-image\">\n",
    "\n",
    "\n",
    "## **1.2 - OpenMP syntax**\n",
    "\n",
    "All OpenMP constructs in C and C++ are indicated with a ```#pragma omp``` followed by parameters, ending in a newline. The pragma usually applies only into the statement immediately following it, except for the ```barrier``` and ```flush``` commands, which do not have associated statements.\n",
    "\n",
    "\n",
    "### **1.2.1 - Directive Format**\n",
    "\n",
    "OpenMP directives are speciﬁed with a directive-speciﬁcation. A directive-speciﬁcation consists of the directive-speciﬁer and any clauses that may optionally be associated with the OpenMP directive. An OpenMP directive may be specified as a pragma directive:\n",
    "  \n",
    "```\n",
    "#pragma omp directive-specification new-line\n",
    "```\n",
    "\n",
    "or a pragma operator:\n",
    "\n",
    "```\n",
    "_Pragma(\"omp directive-specification\")\n",
    "```\n",
    "\n",
    "### **1.2.2 - Clause Format**\n",
    "\n",
    "OpenMP clauses are speciﬁed as part of a directive-speciﬁcation. Clauses are optional and, thus, may be omitted from a directive-speciﬁcation unless otherwise speciﬁed. The order in which clauses appear on directives is not signiﬁcant unless otherwise speciﬁed.\n",
    "\n",
    "```#pragma omp directive-specification clause-name[(clause-argument-speciﬁcation [; clause-argument-speciﬁcation [;...]])]```\n",
    "\n",
    "\n",
    "---\n",
    "\n",
    "## **1.3 - Exploiting Parallelism**\n",
    "\n",
    "This section discuss constructs for generating and controlling parallelism.\n",
    "\n",
    "\n",
    "### **1.3.1 - The Parallel construct**\n",
    "\n",
    "The parallel construct starts a parallel block. It creates a *team* of N threads (where N is determined at runtime, usually from the number of CPU cores), all of which execute the next statement (or the next block). After the statement, the threads join back into one.\n",
    "\n",
    "```\n",
    "int main(int argc, char **argv){\n",
    "    \\* sequential region *\\\n",
    "\n",
    "    #pragma omp parallel\n",
    "    {\n",
    "        \\* parallel region *\\\n",
    "    }\n",
    "\n",
    "    \\* sequential region *\\\n",
    "\n",
    "    return 0;\n",
    "}\n",
    "```\n",
    "\n",
    "Within a ```parallel``` region, thread numbers uniquely identify each thread (from 0 to the number of created threads - 1). A thread can obtain its own thread number by calling the function ```omp_get_thread_num()```. A thread can also get the total number of threads that are running the ```parallel``` region through the function ```omp_get_num_threads()```.\n",
    "\n",
    "If a thread in a ```parallel``` region encounters another ```#pragma omp parallel``` directive, it creates a new team of threads. \n",
    "\n",
    "An implicit barrier occurs at the end of a ```parallel``` region to join all threads. After the end of such region, only the master thread of the team resumes execution.\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "#### Exercise 1: Parallelizing the first code\n",
    "\n",
    "For this exercise, you must apply the ```#pragma omp parallel``` to parallelize the code [hello_seq.c](../src/introduction/hello/hello_seq.c).\n",
    "1. First, compile and run the sequential code to observe that only one ```Hello World``` is printed in the screen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello && gcc hello_seq.c -o hello_seq && ./hello_seq"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Open the code [hello_omp.c](../src/introduction/hello/hello_omp.c), include the libgomp library (```omp.h```), and apply the parallel directive so that multiple ```Hello World``` are printed out. Once you are done, save the file.\n",
    "3. To compile an OpenMP code with GCC compiler, you must include the ```-fopenmp``` flag to the command line: ```gcc file.c -o a.out -fopenmp```. \n",
    "4. Play the next cell to compile and run the binary."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello && gcc hello_omp.c -o hello_omp -fopenmp && ./hello_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "### **1.3.1.1 - Playing with the number of threads**\n",
    "\n",
    "By default, the number of threads that are created to execute each parallel region matches the number of cores in the architecture. However, the user can modify this number through the following ways:\n",
    "1. **Environment Variable**: In the Linux terminal, you can type the following command to define the number of threads equal to 4:\n",
    "    ```\n",
    "    export OMP_NUM_THREADS=4\n",
    "    ```\n",
    "2. **Function**: Inside the code, the user can use the following function to define the number of threads equal to 4:\n",
    "    ```\n",
    "    omp_set_num_threads(4);\n",
    "    ```\n",
    "3. **Clause**: Along with the parallel construct, the user can use the following clause to define the number of threads equal to 4:\n",
    "    ```\n",
    "    #pragma omp parallel num_threads(4)\n",
    "    ```\n",
    "\n",
    "#### Exercise 2: Changing the number of threads\n",
    "\n",
    "For this exercise, you must apply the previous knowledge acquired to change the number of running threads in the parallel region for the code [hello_omp.c](../src/introduction/hello/hello_omp.c).\n",
    "\n",
    "##### 2.A: Through Environment Variable\n",
    "To use the environment variable, you can type it directly into the terminal where the application is running. Try with different number of threads."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello/ && export OMP_NUM_THREADS=4 && ./hello_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.B: Through Function\n",
    "To use the function, you need to write it before the parallel constructor. Therefore, edit the code [here](../src/introduction/hello/hello_omp.c). Once you have finished, save it and play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello/ && gcc hello_omp.c -o hello_omp -fopenmp && ./hello_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.C: Through Clause\n",
    "To use the clause, you just need to write it in the end of the ```#pragma omp parallel``` directive. Therefore, edit the code [here](../src/introduction/hello/hello_omp.c). Once you have finished, save it and play the next cell.\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello/ && gcc hello_omp.c -o hello_omp -fopenmp && ./hello_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### 2.D: Try different approaches\n",
    "\n",
    "After trying the different ways of defining the number of threads, take a time to do the following (For all cases below, you can run the same cell after each edit):\n",
    "1. Create more than one parallel region in the source code and identify each parallel region with a different printf. \n",
    "2. What happens when the number of threads is defined via environment variable?\n",
    "3. What happens when the number of threads is defined via function? Try using this function with different number of threads right before each parallel region.\n",
    "4. What happens when the number of threads is defined via clause? Try using different values for each parallel region.\n",
    "5. Is there a precedence when defining the number of threads?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/hello/ && gcc hello_omp.c -o hello_omp -fopenmp && ./hello_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 3: What is wrong with the code?\n",
    "\n",
    "In this exercise, you will run an application that performs the addVectors operation in parallel. This application is parallelized with only the ```#pragma omp parallel``` directive. You can find the source code [here](../src/introduction/addVectors/addVectors.c). It performs the sum of 8 elements of array *C = A + B*; To run, play the next cell:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. What is the output?\n",
    "2. Why all threads are computing the same indices of each array?\n",
    "3. Take a time to understand what is happening in this exercise. Also, remember that the ```#pragma omp parallel``` directive only creates a team of threads. That is, it does not divide the workload (iterations) among the threads. \n",
    "4. We will cover the worksharing constructor in the next chapter."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1.1.2 - Clauses**\n",
    "\n",
    "#### **1.1.2.1 - private(list)**\n",
    "\n",
    "This clause declares the scope of the data variables in ```list``` to be private to each thread during the parallel region. Data variables in list are separated by commas, as exemplified below for variables ```a``` and ```b``` .\n",
    "\n",
    "```\n",
    "int a, b, c;\n",
    "#pragma omp parallel private(a, b)\n",
    "{\n",
    "    a = omp_get_thread_num();\n",
    "    b = srand();\n",
    "    printf(\"thread id %d generated a random value %d\\n\", a, b);\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "\n",
    "#### **1.1.2.2 - shared(list)**\n",
    "\n",
    "When this clause is employed, the scope of the comma-separated data variables in list are defined to be shared across all threads. By default, all variables are shared among the threads. In the example below, the array ```A``` is declared to be shared.\n",
    "\n",
    "```\n",
    "int A[N];\n",
    "#pragma omp parallel shared(A)\n",
    "{\n",
    "    int sum_per_thread = 0;\n",
    "    for(int i = 0; i < N; i++){\n",
    "        sum_per_thread += A[i] * omp_get_thread_num();\n",
    "    }    \n",
    "}\n",
    "```\n",
    "\n",
    "#### **1.1.2.3 - firstprivate(list)**\n",
    "\n",
    "When this clause is applied to a parallel region, the scope of the data variables in ```list``` to be private to each thread. Different from the ```private``` clause, each new private variable is initialized with the value of the original variable as if there was an implied declaration within the statement block. Also, data variables in list are separated by commas. In the example below, the printed values for ```a``` and ```b``` should be 100 and 10, respectively.\n",
    "\n",
    "```\n",
    "int a = 100, b = 10, c;\n",
    "#pragma omp parallel private(c) firstprivate(a, b)\n",
    "{\n",
    "    printf(\"thread id %d with values a (%d), b(%d) and c(%d)\\n\", omp_get_thread_num(), a, b, c);\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "#### **1.1.2.4 - num_threads(int n)**\n",
    "\n",
    "When this clause is employed, the value of ```n``` is an integer expression that specifies the number of threads to use for the parallel region. If dynamic adjustment of the number of threads is also enabled, then ```n``` specifies the maximum number of threads to be used. In the example below, 16 threads should be created and each one should print its id along with the number 16.\n",
    "\n",
    "```\n",
    "int nThreads = 16;\n",
    "int idThread, totalThreads;\n",
    "#pragma omp parallel num_threads(nThreads) private(idThread) shared(totalThreads)\n",
    "{\n",
    "    idThread = omp_get_thread_num();\n",
    "    totalThreads = omp_get_num_threads();\n",
    "    printf(\"I am thread %d from a total of %d threads\\n\", idThread, totalThreads);       \n",
    "}\n",
    "```\n",
    "\n",
    "\n",
    "#### **1.1.2.5 - reduction(operator: list)**\n",
    "\n",
    "This clause performs a reduction on all scalar variables in ```list``` using the specified ```operator```. Reduction variables in list are separated by commas. When it is employed, a private copy of each variable in list is created for each thread. At the end of the statement block, the final values of all private copies of the reduction variable are combined in a manner appropriate to the operator, and the result is placed back in the original value of the shared reduction variable. For example, when the max operator is specified, the original reduction variable value combines with the final values of the private copies by using the following expression:\n",
    "\n",
    "```\n",
    "    original_reduction_variable = original_reduction_variable < private_copy ?\n",
    "    private_copy : original_reduction_variable;\n",
    "```\n",
    "\n",
    "When the programming language is C or C++, the following operators can be used.\n",
    " \n",
    "<table><tr><th > Identifier\t<th><th>   Initializer <th><th>   Combiner <tr><tr>\n",
    "<tr><td> +\t                <td><td>   omp_priv = 0\t            <td><td>    omp_out += omp_in <tr><tr>\n",
    "<tr><td> -\t                <td><td>   omp_priv = 0\t            <td><td>    omp_out += omp_in <tr><tr>\n",
    "<tr><td> *\t                <td><td>   omp_priv = 1\t            <td><td>    omp_out *= omp_in <tr><tr>\n",
    "<tr><td> &\t                <td><td>   omp_priv = ~ 0\t        <td><td>    omp_out &= omp_in <tr><tr>\n",
    "<tr><td> |\t                <td><td>   omp_priv = 0\t            <td><td>    omp_out |= omp_in <tr><tr>\n",
    "<tr><td> ^\t                <td><td>   omp_priv = 0\t            <td><td>    omp_out ^= omp_in <tr><tr>\n",
    "<tr><td> &&\t            <td><td>   omp_priv = 1\t                <td><td>    omp_out = omp_in && omp_out <tr><tr>\n",
    "<tr><td> ||\t            <td><td>   omp_priv = 0\t                <td><td>    omp_out = omp_in || omp_out <tr><tr>\n",
    "<tr><td> max\t            <td><td>   omp_priv = Least representable number in the reduction list item type\t<td><td>    omp_out = omp_in > omp_out ? omp_in : omp_out <tr><tr>\n",
    "<tr><td> min\t            <td><td>   omp_priv = Largest representable number in the reduction list item type\t<td><td>    omp_out = omp_in < omp_out ? omp_in : omp_out <tr><tr><table>\n",
    "\n",
    "The following example shows the reduction ```+``` operation over the variable ```sum```.\n",
    "\n",
    "```\n",
    "int sum=0;\n",
    "#pragma omp parallel reduction(+:sum)\n",
    "{\n",
    "    int idThread = omp_get_thread_num();\n",
    "    sum += idThread;    \n",
    "}\n",
    "printf(\"The sum of all thread ids is: %d\\n\", sum);       \n",
    "```\n",
    "\n",
    "### **1.3.2 - Work-sharing constructs**\n",
    "\n",
    "A work-sharing construct delegates the execution of the corresponding region among the threads within its designated thread team. Threads execute portions of the parallel region. \n",
    "\n",
    "### **1.3.2.1 - \\#pragma omp for**\n",
    "\n",
    "The ```omp for``` directive informs the compiler to distribute loop iterations within the team of threads that reaches this constructor. The syntax is ```#pragma omp for clauses```, where the clauses are optional and will be discussed next.\n",
    "\n",
    "A simple example can be seen below, where the number of iterations ```N``` will be divided among the threads that are created in the parallel directive. In this scenario, each created thread will be responsible for executing a different set of iterations.\n",
    "\n",
    "```\n",
    "#pragma omp parallel\n",
    "{\n",
    "    #pragma omp for\n",
    "    for(int i = 0; i < N; i++){\n",
    "        \\* loop operations in parallel *\\\n",
    "    }\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "The ```pragma omp for``` directive can be combined with the ```pragma omp parallel```. In this scenario, the following code has the very same effect as the previous one.\n",
    "\n",
    "```\n",
    "#pragma omp parallel for\n",
    "for(int i = 0; i < N; i++){\n",
    "    \\* loop operations in parallel *\\\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "#### Exercise 4: Applying the Work-sharing constructor for the addVectors code\n",
    "\n",
    "In this exercise, you will modify the [addVectors](../src/introduction/addVectors/addVectors.c) application so that the iterations of the loop are distributed among the threads in the parallel region through the work-sharing construct.\n",
    "After editing and saving the code, play the following cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1. What is the output? \n",
    "2. Are the threads computing different indices of each array?\n",
    "3. Change the number of threads that are created in the parallel region and run the cell below again. What happens?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **1.3.2.1.1 - schedule(type) clause**\n",
    "\n",
    "This clause specifies how iterations of the for loop are divided among available threads. Acceptable values for ```type``` are:\n",
    "\n",
    "- **static**: Iterations of a loop are divided into chunks of size *ceiling(number_of_iterations/number_of_threads)*. Each thread is assigned a separate chunk. This scheduling policy is also known as block scheduling.\n",
    "\n",
    "- **static,n**: Iterations of a loop are divided into chunks of size *n*. Each chunk is assigned to a thread in round-robin fashion. *n* must be an integral assignment expression of value 1 or greater.\n",
    "\n",
    "- **dynamic**: Iterations of a loop are divided into chunks of size *ceiling(number_of_iterations/number_of_threads)*.\n",
    "Chunks are dynamically assigned to active threads on a \"first-come, first-do\" basis until all work has been assigned.\n",
    "\n",
    "- **dynamic,n**: As above, except chunks are set to size *n*. *n* must be an integral assignment expression of value 1 or greater.\n",
    "\n",
    "- **guided**: Chunks are made progressively smaller until the default minimum chunk size is reached. The first chunk is of size *ceiling(number_of_iterations/number_of_threads)*. Remaining chunks are of size *ceiling(number_of_iterations_left/number_of_threads)*. The minimum chunk size is 1. Chunks are assigned to active threads on a \"first-come, first-do\" basis until all work has been assigned.\n",
    "\n",
    "- **guided,n**: As above, except the minimum chunk size is set to *n*; *n* must be an integral assignment expression of value 1 or greater.\n",
    "\n",
    "- **runtime**: Scheduling policy is determined at run time. Use the OMP_SCHEDULE environment variable to set the scheduling type and chunk size.\n",
    "\n",
    "- **auto**: the scheduling is delegated to the compiler and runtime system. The compiler and runtime system can choose any possible mapping of iterations to threads (including all possible valid schedules) and these may be different in different loops.\n",
    "\n",
    "\n",
    "<img src=\"../imgs/scheduling.png\" alt=\"alt text\" width=\"800\" height=\"450\" class=\"blog-image\">\n",
    "\n",
    "source of image: https://www.micc.unifi.it/bertini/download/parallel/2016-2017/9_shared_memory_openmp_directives.pdf"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### Exercise 5: Playing with different scheduler types.\n",
    "\n",
    "In this exercise, you will modify the [addVectors](../src/introduction/addVectors/addVectors.c) application so that the iterations of the loop are distributed among the threads in the parallel region considering the types defined above. For that, try the following:\n",
    "1. Use the clause ```schedule(static,3)```. Play the next cell. What is the output?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "2. Use the clause ```schedule(dynamic,2)```. Play the next cell. What is the output?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "3. Use the clause ```schedule(guided,2)```. Play the next cell. What is the output?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "4. Repeat the process above changing the type and the chunksize. Also, change the value of ```N``` so the behavior of each schedule type can be better seen."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors.c -o addVectors -fopenmp && ./addVectors"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### **1.2.1.2 - nowait clause**\n",
    "\n",
    "This clause can be employed to avoid the implied barrier at the end of the ```for``` directive. This is useful when there are multiple independent work-sharing sections or iterative loops within a given parallel region. Only one nowait clause can appear on a given for directive. The example below describes the usage on a parallel region with two loops.\n",
    "\n",
    "\n",
    "```\n",
    "#pragma omp parallel\n",
    "{\n",
    "    #pragma omp for nowait\n",
    "    for(int i = 0; i < N; i++){\n",
    "        \\* loop operations in parallel *\\\n",
    "    }\n",
    "\n",
    "    #pragma omp for nowait\n",
    "    for(int i = 0; i < N; i++){\n",
    "        \\* loop operations in parallel *\\\n",
    "    }\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "#### **1.3.2.1.3 - collapse(n) clause**\n",
    "\n",
    "When this clause is employed, it allows you to parallelize *n* multiple loops in a nest without introducing nested parallelism.\n",
    "For that, the loops must form a rectangular iteration space and the bounds and stride of each loop must be invariant over all the loops. If the loop indices are of different size, the index with the largest size will be used for the collapsed loop.\n",
    "The loops must be perfectly nested; that is, there is no intervening code nor any OpenMP pragma between the loops which are collapsed. \n",
    "The associated do-loops must be structured blocks. Their execution must not be terminated by a **break** statement.\n",
    "If multiple loops are associated to the loop construct, only an iteration of the innermost associated loop may be curtailed by a continue statement. If multiple loops are associated to the loop construct, there must be no branches to any of the loop termination statements except for the innermost associated loop.\n",
    "\n",
    "The following example depicts the parallelization of two loops that are collapsed.\n",
    "\n",
    "```\n",
    "#pragma omp parallel for collapse(2)\n",
    "for(int i = 0; i < N; i++){\n",
    "    for(int j = 0; j < N; j++){\n",
    "        \\* loop operations in parallel *\\\n",
    "    }\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "#### **1.3.2.1.4 - ordered clause**\n",
    "\n",
    "When this clause is employed, during execution of an iteration of a loop or a loop nest within a loop region, the executing thread must not execute more than one ordered region which binds to the same loop region. As a consequence, if multiple loops are associated to the loop construct by a collapse clause, the ordered construct has to be located inside all associated loops.\n",
    "\n",
    "\n",
    "### **1.3.2.2 - \\#pragma omp single**\n",
    "\n",
    "The ```single``` construct specifies that the associated structured block is executed by only one of the threads in the team (not necessarily the master thread), in the context of its implicit task. The other threads in the team, which do not execute the block, wait at an implicit barrier at the end of the single construct unless a nowait clause is specified. In the following example, only one thread will execute the printf operation.\n",
    "\n",
    "```\n",
    "#pragma omp parallel\n",
    "{\n",
    "    \\* operations done in parallel *\\\n",
    "    \n",
    "    #pragma omp single\n",
    "    {\n",
    "        printf(\"Total number of threads: %d\\n\", omp_get_num_threads());\n",
    "    }\n",
    "    \\* operations done in parallel *\\\n",
    "\n",
    "}\n",
    "\n",
    "```\n",
    "\n",
    "### **1.3.2.3 - \\#pragma omp sections**\n",
    "\n",
    "When this work-sharing constructor is employed, a set of structured blocks are distributed among and executed by the threads in a team. Each structured block is executed once by one of the threads in the team in the context of its implicit task. The following example depicts the execution of two operations in parallel by two threads (each thread executes a different section).\n",
    "\n",
    "\n",
    "```\n",
    "#pragma omp parallel\n",
    "{\n",
    "    #pragma omp sections\n",
    "    { \n",
    "        #pragma omp section \n",
    "        {\n",
    "            printf(\"Thread %d is running the first structured block\\n\", omp_get_thread_num());\n",
    "        } \n",
    "        #pragma omp section \n",
    "        {\n",
    "            printf(\"Thread %d is running the second structured block\\n\", omp_get_thread_num());\n",
    "        } \n",
    "   }\n",
    "}\n",
    "```\n",
    "\n",
    "When this work-sharing is employed, the parallelization scheme is very similar to the one applied by POSIX Threads. In this scenario, the programmer is responsible for dividing the workload among threads in sections.\n",
    "\n",
    "#### Exercise 6: Applying sections to the addVectors code\n",
    "\n",
    "In this exercise, you will modify the [addVectorsSections](../src/introduction/addVectors/addVectors_sections.c) application so that the parallelization scheme employed is ```sections```. In this scenario, consider that **two** threads will be created (and hence, two sections) and the iterations of the loop are distributed equaly among the threads.\n",
    "After editing and saving the code, play the following cell.\n",
    "Take a time to change the number of threads that are created. What happens with the execution? Are all the threads executing the parallel region (how can you check this?)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/addVectors/ && gcc addVectors_sections.c -o addVectors_sections -fopenmp && ./addVectors_sections"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "---"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## **1.4 - Final Exercises**\n",
    "\n",
    "### **1.4.1 - Fast Fourier Transform**\n",
    "\n",
    "A C code which demonstrates the computation of a Fast Fourier Transform (FFT), and is intended as a starting point for developing a parallel version using OpenMP. The source code of the sequential version can be found [here](../src/introduction/exercises/fft.c). Your objective is to develop a parallel version with OpenMP.\n",
    "\n",
    "To run the sequential code, play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc fft.c -o fft -lm -O3 && ./fft"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The OpenMP code to be parallelized can be found [here](../src/introduction/exercises/fft_omp.c).\n",
    "\n",
    "After parallelizing the code with OpenMP, you can play the next cell to check if the parallelization is correct.\n",
    "\n",
    "PS: If you intend to observe the real speedup of your implementation, the ideal is to execute the code in a physical machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc fft_omp.c -o fft_omp -lm -O3 -fopenmp && export OMP_NUM_THREADS=2 && ./fft_omp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1.4.2 - Heated Plate**\n",
    "\n",
    "The Heated Plate is a C code which solves the steady state heat equation in a 2D rectangular region, and is intended as a starting point for implementing an OpenMP parallel version. The sequential version of the code can be found [here](../src/introduction/exercises/heat.c). Your objective is to develop a parallel version with OpenMP.\n",
    "\n",
    "To run the sequential code, play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc heat.c -o heat -lm -O3 && ./heat 8192 out_heated_plated_seq.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The OpenMP code to be parallelized can be found [here](../src/introduction/exercises/heat_omp.c).\n",
    "\n",
    "After parallelizing the code with OpenMP, you can play the next cell to check if the parallelization is correct.\n",
    "\n",
    "PS: If you intend to observe the real speedup of your implementation, the ideal is to execute the code in a physical machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc heat_omp.c -o heat_omp -lm -O3 -fopenmp && export OMP_NUM_THREADS=2 && ./heat 8192 out_heated_plated_omp.txt"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1.4.3 - Molecular Dynamics Simulation**\n",
    "\n",
    "This code implements a simple molecular dynamics simulation. \n",
    "\n",
    "The computation involves following the paths of particles which exert a distance-dependent force on each other. The particles are not constrained by any walls; if particles meet, they simply pass through each other.\n",
    "\n",
    "The problem is treated as a coupled set of differential equations. The system of differential equation is discretized by choosing a discrete time step. Given the position and velocity of each particle at one time step, the algorithm estimates these values at the next time step.\n",
    "\n",
    "To compute the next position of each particle requires the evaluation of the right hand side of its corresponding differential equation. Since each of these calculations is independent, there is a potential speedup if the program can take advantage of parallel computing.\n",
    "\n",
    "The sequential version of the code can be found [here](../src/introduction/exercises/md.c). Your objective is to develop a parallel version with OpenMP.\n",
    "\n",
    "To run the sequential code, play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc md.c -o md -lm -O3 && ./md 2 1024 1024 0.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The OpenMP code to be parallelized can be found [here](../src/introduction/exercises/md_omp.c).\n",
    "\n",
    "After parallelizing the code with OpenMP, you can play the next cell to check if the parallelization is correct.\n",
    "\n",
    "PS: If you intend to observe the real speedup of your implementation, the ideal is to execute the code in a physical machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc md_omp.c -o md_omp -lm -O3 -fopenmp && export OMP_NUM_THREADS=2 && ./md 2 1024 1024 0.1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1.4.4 - Prime Numbers**\n",
    "\n",
    "This code counts the number of primes between 1 and N. The algorithm is completely naive. For each integer I, it simply checks whether any smaller J evenly divides it.\n",
    "\n",
    "The sequential version of the code can be found [here](../src/introduction/exercises/prime.c). Your objective is to develop a parallel version with OpenMP.\n",
    "\n",
    "To run the sequential code, play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc prime.c -o prime -lm -O3 && ./prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The OpenMP code to be parallelized can be found [here](../src/introduction/exercises/prime_omp.c).\n",
    "\n",
    "After parallelizing the code with OpenMP, you can play the next cell to check if the parallelization is correct.\n",
    "\n",
    "PS: If you intend to observe the real speedup of your implementation, the ideal is to execute the code in a physical machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc prime_omp.c -o prime_omp -lm -O3 -fopenmp && export OMP_NUM_THREADS=2 && ./prime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### **1.4.5 - Satisfy**\n",
    "\n",
    "This code performs, for a particular circuit, an exhaustive search for solutions of the circuit satisfy problem. It assumes that we are given a logical circuit of AND, OR, and NOT gates, with N binary inputs and a single output. We are to determine all inputs which produce a 1 as the output. The general problem is NP complete, so there is no known polynomial-time algorithm to solve the general case.\n",
    "\n",
    "The example circuit considered here has been described in conjunctive normal form (\"CNF\"). This is a standard format for logical formulas. At the highest level, the formula consists of clauses joined by the AND (conjunction) operator. Each clause consists of signed literals joined by the OR (disjunction) operator. Each signed literal is either the name of a variable (positive literal), or the name of a variable preceded by the NOT (negation) operator (a negative literal). There is a CNF file format that can be used to store logical formulas that have been cast into conjunctive normal form.\n",
    "\n",
    "The sequential version of the code can be found [here](../src/introduction/exercises/satisfy.c). Your objective is to develop a parallel version with OpenMP.\n",
    "\n",
    "To run the sequential code, play the next cell."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc satisfy.c -o satisfy -lm -O3 && ./satisfy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The OpenMP code to be parallelized can be found [here](../src/introduction/exercises/satisfy_omp.c).\n",
    "\n",
    "After parallelizing the code with OpenMP, you can play the next cell to check if the parallelization is correct.\n",
    "\n",
    "PS: If you intend to observe the real speedup of your implementation, the ideal is to execute the code in a physical machine."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "!cd ../src/introduction/exercises/ && gcc satisfy_omp.c -o satisfy_omp -lm -O3 -fopenmp && export OMP_NUM_THREADS=2 && ./satisfy"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "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.10.8"
  },
  "orig_nbformat": 4
 },
 "nbformat": 4,
 "nbformat_minor": 2
}