Suppose the run-time of a serial program is given by T_serial = n^2, where the u

Question

Suppose the run-time of a serial program is given by T_serial = n^2, where the units of the run-time are in microseconds. Suppose that a parallelization of this program has run-time T_parallel = n^2/p + log_2(p). Write a program that finds the speedups and efficiencies of this program for various values of n and p. Run your program with n = 10, 20, 30, 40, ..., 320. and p = 1, 2, 4, ..., 128. What happens to the speedups and efficiencies as p is increased and n is held fixed? What happens when p is fixed and n is increased? Suppose that T_parallel = T_serial/p + T_overhead. Also suppose that we fix p and increase the problem size. Show that if T_overhead grows more slowly than T_serial, the parallel efficiency will increase as we increase the problem size. Show that if, on the other hand. T_overhead grows faster than T_serial, the parallel efficiency will decrease as we increase the problem size.

Explanation / Answer

#include stdio.h
#include math.h
#define aMin 10
#define aMax 320
#define bMin 1
#define bMax 128
Void printHorizontall Separator (int min, int max)
{
int j;
printf(" +");
for(j=min;j max;j*=2)
{
print’f("----------");
}
printf("---+");
}
double Tserial(int a)
{
return pow(a,2);
}
double Tparallela(int a, int b)
{
return Tserial(a)/b + log(b)/log(2);
}
double Tparallelb(int a, int b, int Toverhead)
{
return Tserial(a)/b + Toverhead;
}
double speedupX(int a, int b)
{
return Tserial(a)/Tparallela(a,b);
}
double efficiencyX(int a, int b)
{
return Tserial(a)/(b*Tparallela(a,b));
}

double efficiencyY(int a, int b, intToverhead)
{
return Tserial (a) /(b*Tparallelb(a,b,Toverhead));
}
int main()
{

int a;
int p;
printf("serial program is Tserial = a^2 , where");
printf("the units of run-time are microseconds. Suppose a paral-");
printf("lelization of program has run-time Tparallel = a^2 /b + log 2
(b). Write c ");
printf("program it finds speedups ,efficiencies of
program for vari-");
printf("values a and p. Run your program with a= 10, 20, . . .
, 320, and");
printf("b = 1, 2, 4, 16,. . . , 128. efficiencie b");
printf("What happens for b is fixed
and a isincreased?");

printf("Rows indicate the number of processes (p)Columns indicate the
problem size(a)");

printf(" Speedup");

printHorizontalSeparator(aMin,aMax);

print’f(" ");
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.d",a);
}
printf("|");
printHorizontal Separator(aMin,nMax);
//data
for(b=bMin;b =bMax;b*=2)
{
printf(" %8.d",b);
for(a=nMin;a =aMax;a*=2)
{
printf("|%8.4f",speedupX(a,b));
}
printf("|");
}
printHorizontalSeparator(aMin,aMax);
printf("");

printf(" Efficiency");
printHorizontalSeparator(aMin,aMax);

printf(" ");
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.d",a);
}
printf("|);
printHorizontalSeparator(aMin,aMax);
for(p=Min;b =bMax;b*=2)
{
printf(" %8.d",p);
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.4f", efficiencyX(n,p));
}
printf("|");
}
//base on the table
printHorizontalSeparator(aMin,aMax);

printf("");
printf("Tparallel = Tserial /b + Toverhead . we fix b and increase size.");
printf(" - Show that if Toverhead grows slowly than Tserial ,
parallel efficiency will increases as increase problem size.");
printf(" - and, T overhead faster
, the parallel efficiency ,decrease as increase problem size.");

printf(" Efficiency for Toverhead=a");
//hat on the table
printHorizontalSeparator(aMin,aMax);
printf(" ");
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.d",a);
}
printf("|");
//separator between headings and data
printHorizontalSeparator(aMin,aMax);

for(b=Min;b =bMax;b*=2)
{
printf(" %8.d",b);
for((a=aMin;a =aMax;a*=2)
{
printf("|%8.6f",efficiencyB(a,b,a));
}
printf("| ");
}
//base on the table
printHorizontalSeparator(aMin,aMax);
//spaces between tables
printf("");
//Table Label
printf(" Efficiency forToverhead=a^3");
//hat on the table
printHorizontalSeparator(aMin,aMax);

printf(" ");
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.d",a);
}
printf("|");
//separator between headings and data
printHorizontalSeparator(aMin,aMax);
//data
for(b=bMin;b =bMax;b*=2)
{
printf(" %8.d",b);
for(a=aMin;a =aMax;a*=2)
{
printf("|%8.6f",efficiencyB(a.b,a*a*a));
}
printf("|");
}
printHorizontalSeparator(aMin,aMax);
//spaces between tables
printf("");
return 0;

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.