Question

Assume that a computation comprises k + 1 distinct tasks. In order to prepare a program for the desired computation, each of these tasks has been written as a function in the C language. The k+1 functions are labeled T0(), T1(), . . . , Tk(). Each function requires τ time units to execute. Due to data dependencies, functions T1() to Tk() must be executed after function T0(). There are no data dependencies among the functions T1() to Tk().

(a) Using the given functions, write a C program that executes on a single processor.
(b)Write an equivalent C program that executes on k processors.
(c) Derive an expression for the ideal speedup for the program in part (b) relative to the
program in part (a).

Answer 1

To write a C program that executes on a single processor, use a sequential control flow. For a program that executes on k processors, use parallel processing with threads. The ideal speedup for the parallel program can be calculated using Amdahl's law.

Step-by-step explanation:

To write a C program that executes on a single processor, you can use a sequential control flow. First, execute function T0() and then execute functions T1() to Tk() in order. Here's an example:

int main() {
T0();
T1();
...
Tk();
return 0;
}

To write an equivalent C program that executes on k processors, you can use parallel processing. Use k threads to execute functions T1() to Tk() simultaneously, while the main thread executes function T0(). Here's an example using thread libraries:

#include

void* thread_func(void* arg) {
// Execute functions T1() to Tk()
return NULL;
}

int main() {
pthread_t threads[k];
pthread_create(&threads[0], NULL, thread_func, NULL);
T0();
pthread_join(threads[0], NULL);
return 0;
}

The ideal speedup for the program in part (b) relative to the program in part (a) can be derived using Amdahl's law. The speedup can be calculated using the formula:

Speedup = 1 / (f + (1 - f)/k)

Where f is the fraction of the program that is serialized and k is the number of processors. In this case, f is the time taken by function T0() divided by the total time taken to execute all functions. The formula assumes that the functions are executed independently and have equal execution times.