uni

University stuff
git clone git://git.margiolis.net/uni.git
Log | Files | Refs | README | LICENSE

ex1.c (3537B)


      1 #include <err.h>
      2 #include <stdarg.h>
      3 #include <stdio.h>
      4 #include <stdlib.h>
      5 
      6 #include <omp.h>
      7 
      8 #define abs(x)	((x) < 0 ? -(x) : (x))
      9 
     10 static void	*emalloc(size_t);
     11 static int	safe_input(const char *, ...);
     12 static void	pretty_print(int **, int, const char *);
     13 static int	strictly_diagonal_dominant(int **, int);
     14 static int	diagonal_max(int **, int);
     15 static int	**new_array(int **, int, int);
     16 static int	calc_min(int **, int);
     17 
     18 /*
     19  * Fail-safe malloc(3).
     20  */
     21 static void *
     22 emalloc(size_t nb)
     23 {
     24 	void *p;
     25 
     26 	if ((p = malloc(nb)) == NULL)
     27 		err(1, "malloc");
     28 
     29 	return (p);
     30 }
     31 
     32 static int
     33 safe_input(const char *fmt, ...)
     34 {
     35 	va_list args;
     36 	char buf[48];
     37 	int n, rc;
     38 
     39 	/* Collect the arguments into a buffer. */
     40 	va_start(args, fmt);
     41 	vsnprintf(buf, sizeof(buf), fmt, args);
     42 	va_end(args);
     43 
     44 	/*
     45 	 * The following loop keeps asking for input as long as the current
     46 	 * input wasn't correct. In this case "incorrect" input means anything
     47 	 * other than digits.
     48 	 */
     49 	do {
     50 		printf("\r%s", buf);
     51 		rc = scanf("%d", &n);
     52 		(void)getchar();
     53 	} while (rc != 1);
     54 
     55 	return (n);
     56 }
     57 
     58 /*
     59  * Print the contents of a 2D array like:
     60  *
     61  * array = [
     62  *	[x, y, z]
     63  *	[x, y, z]
     64  * ]
     65  */
     66 static void
     67 pretty_print(int **arr, int n, const char *name)
     68 {
     69 	int i, j;
     70 
     71 	printf("\n%s = [\n", name);
     72 	for (i = 0; i < n; i++) {
     73 		printf("\t[");
     74 		for (j = 0; j < n; j++) {
     75 			printf("%d%s", arr[i][j],
     76 			   (j == n - 1) ? "]\n" : ", ");
     77 		}
     78 	}
     79 	printf("]\n");
     80 }
     81 
     82 static int
     83 strictly_diagonal_dominant(int **a, int n)
     84 {
     85 	int i, j, sum, flag = 1;
     86 
     87 #pragma omp parallel for
     88 	for (i = 0; i < n; i++) {
     89 		for (j = 0; j < n; j++) {
     90 			if (i == j)
     91 				continue;
     92 			sum += abs(a[i][j]);
     93 		}
     94 		if (abs(a[i][i]) <= sum)
     95 			flag = 0;
     96 	}
     97 
     98 	return (flag);
     99 }
    100 
    101 static int
    102 diagonal_max(int **a, int n)
    103 {
    104 	int i, max;
    105 
    106 	max = a[0][0];
    107 #pragma omp parallel for reduction(max : max)
    108 	for (i = 0; i < n; i++) {
    109 		if (abs(a[i][i]) > max)
    110 			max = a[i][i];
    111 	}
    112 
    113 	return (max);
    114 }
    115 
    116 static int **
    117 new_array(int **a, int m, int n)
    118 {
    119 	int **b, i, j;
    120 
    121 	b = emalloc(n * sizeof(int *));
    122 #pragma omp parallel for
    123 	for (i = 0; i < n; i++) {
    124 		b[i] = emalloc(n * sizeof(int));
    125 		for (j = 0; j < n; j++)
    126 			b[i][j] = m - a[i][j];
    127 	}
    128 
    129 	return (b);
    130 }
    131 
    132 static int
    133 calc_min(int **b, int n)
    134 {
    135 	int i, j, min;
    136 
    137 	/* with reduction */
    138 	min = b[0][0];
    139 #pragma omp parallel for reduction(min : min)
    140 	for (i = 0; i < n; i++) {
    141 		for (j = 0; j < n; j++) {
    142 			if (b[i][j] < min)
    143 				min = b[i][j];
    144 		}
    145 	}
    146 
    147 	/* without reduction, with critical region protection */
    148 	min = b[0][0];
    149 #pragma omp parallel for private(i, j) shared(min)
    150 	for (i = 0; i < n; i++) {
    151 		for (j = 0; j < n; j++) {
    152 #pragma omp critical
    153 		{
    154 			if (b[i][j] < min)
    155 				min = b[i][j];
    156 		}
    157 		}
    158 	}
    159 
    160 	/* XXX: didn't implement binary tree method */
    161 
    162 	return (min);
    163 }
    164 
    165 int
    166 main(int argc, char *argv[])
    167 {
    168 	int **a, **b;
    169 	int i, j, m, min, n, ntd;
    170 	double start, end;
    171 
    172 	ntd = safe_input("threads: ", 0);
    173 	omp_set_num_threads(ntd);
    174 
    175 	n = safe_input("n: ", 0);
    176 	a = emalloc(n * sizeof(int *));
    177 	for (i = 0; i < n; i++) {
    178 		a[i] = emalloc(n * sizeof(int));
    179 		for (j = 0; j < n; j++)
    180 			a[i][j] = safe_input("a[%d][%d]: ", i, j);
    181 	}
    182 
    183 	start = omp_get_wtime();
    184 
    185 	if (strictly_diagonal_dominant(a, n)) {
    186 		m = diagonal_max(a, n);
    187 		b = new_array(a, m, n);
    188 		min = calc_min(b, n);
    189 
    190 		pretty_print(a, n, "A");
    191 		pretty_print(b, n, "B");
    192 		printf("Diagonal max: %d\n", m);
    193 		printf("Min: %d\n", min);
    194 
    195 		free(b);
    196 	} else
    197 		printf("not strictly diagonal dominant\n");
    198 
    199 	end = omp_get_wtime();
    200 	printf("Total time: %f seconds\n", end - start);
    201 
    202 	free(a);
    203 
    204 	return (0);
    205 }