Question

The baseline execution time of a program on a \( 2 \, \text{GHz} \) single core machine is \( 100 \, \text{ns} \). The code corresponding to \( 90\% \) of the execution time can be fully parallelized. The overhead for using an additional core is \( 10 \, \text{ns} \) when running on a multicore system. Assume that all cores in the multicore system run their share of the parallelized code for an equal amount of time. The number of cores that minimize the execution time of the program is \_\_\_\_\_.

Answer 1

Step 1: Divide the execution time into parallel and serial components. The program's execution time is \( 100 \, \text{ns} \). The parallelizable part is \( 90\% \), and the non-parallelizable part is \( 10\% \): \[ \text{Parallelizable time} = 90 \, \text{ns}, \quad \text{Non-parallelizable time} = 10 \, \text{ns}. \] Step 2: Calculate the execution time for \( k \) cores. Using Amdahl's Law and considering overhead, the execution time is given by: \[ T_k = \frac{\text{Parallelizable time}}{k} + \text{Non-parallelizable time} + (k - 1) \times \text{Overhead}. \] Substitute values: \[ T_k = \frac{90}{k} + 10 + 10 \times (k - 1). \] Step 3: Minimize \( T_k \). For \( k = 3 \): \[ T_3 = \frac{90}{3} + 10 + 10 \times (3 - 1) = 30 + 10 + 20 = 60 \, \text{ns}. \] Checking \( k = 2 \) and \( k = 4 \), \( T_3 \) is minimum. Final Answer: \[ \boxed{3} \]