commit ecf51563722f52a5c010c9890c86f88d26a55126
parent c7ba5d17c2709fd46eb48bc454baf4e39ff1e556
Author: Christos Margiolis <christos@margiolis.net>
Date: Fri, 9 Dec 2022 23:23:18 +0200
finished ex1
Diffstat:
12 files changed, 228 insertions(+), 22 deletions(-)
diff --git a/c_parallel_systems/ex1/Makefile b/c_parallel_systems/ex1/Makefile
@@ -4,7 +4,7 @@ all:
cc ${TARG}.c -fopenmp -lomp -o ${TARG}
clean:
- rm ${TARG}
+ rm -f ${TARG} *.core
run:
./${TARG}
diff --git a/c_parallel_systems/ex1/doc.pdf b/c_parallel_systems/ex1/doc.pdf
Binary files differ.
diff --git a/c_parallel_systems/ex1/doc.tex b/c_parallel_systems/ex1/doc.tex
@@ -0,0 +1,132 @@
+\documentclass{article}
+\usepackage[utf8]{inputenc}
+\usepackage[greek,english]{babel}
+\usepackage{alphabeta}
+\usepackage{fancyhdr}
+\usepackage{listings}
+\usepackage{mathtools}
+\usepackage{xcolor}
+\usepackage{biblatex}
+\usepackage[left=1cm,right=1cm]{geometry}
+
+\lstset {
+ basicstyle=\ttfamily,
+ columns=fullflexible,
+ breaklines=true,
+ keepspaces=true,
+ showstringspaces=false
+}
+
+\title{Εργαστήριο Παράλληλων Συστημάτων - Εργασία 1}
+\author{Χρήστος Μαργιώλης}
+\date{Δεκέμβριος 2022}
+
+\begin{document}
+
+\begin{titlepage}
+ \maketitle
+\end{titlepage}
+
+\renewcommand{\contentsname}{Περιεχόμενα}
+\tableofcontents
+\pagebreak
+
+\section{Κώδικας}
+
+Ο κώδικας έχει σχόλια μόνο στα σημεία που θεώρησα ότι μπορεί να προκύψει κάποιο
+«μπέρδεμα».
+
+\lstinputlisting[language=C]{ex1.c}
+
+\section{Προβλήματα}
+
+Δεν κατάφερα να υλοποιήσω τον υπολογισμό του ελάχιστο με χρήση αλγορίθμου
+δυαδικού δέντρου (ερώτημα d2.2).
+
+\section{Βοηθητικό script}
+
+\lstinputlisting[language=sh]{randinput}
+
+Το script \lstinline{randinput} (δεν τρέχει σε Windows) δέχεται ως είσοδο τον
+αριθμό των νημάτων, καθώς και το $N$. Στην συνέχεια τυπώνει (με την
+συγκεκριμένη σειρά) τον αριθμό των νημάτων, το $N$, και $N$ τυχαίους αριθμούς.
+Αυτό είναι χρήσιμο στο να μπορούμε να κάνουμε δοκιμές με διαφορετικά δεδομένα
+(ειδικά για μεγάλες τιμές $N$) χωρίς να πρέπει να δώσουμε τα δεδομένα
+χειροκίνητα.
+
+Η χρήση του script έχει ως εξής:
+
+\begin{lstlisting}
+usage: randinput nthreads N
+\end{lstlisting}
+
+Παρακάτω φαίνεται μία ενδεικτική χρήση:
+
+\begin{lstlisting}
+$ ./randinput 2 3
+2
+3
+8
+0
+1
+5
+1
+2
+0
+4
+8
+\end{lstlisting}
+
+'Αρα έχουμε 2 νήματα, έναν πίνακα $3x3$, τα στοιχεία του οποίου είναι:
+\[[[8, 0, 1], [5, 1, 2], [0, 4, 8]]\]
+
+Τώρα, μπορούμε να διοχετεύσουμε την έξοδο του script σε ένα αρχείο και να το
+δώσουμε ως είσοδο στο κύριο πρόγραμμα:
+
+\begin{lstlisting}
+./randinput 2 3 > input.txt
+\end{lstlisting}
+
+\section{Ενδεικτικά τρεξίματα}
+
+\textit{Σημειώνεται ότι το πρόγραμμα τρέχει κανονικά και χωρίς αρχείο για είσοδο.}
+
+Για 2 threads και $A = 4x4$:
+
+\includegraphics[width=\textwidth]{res/run1.png} \\
+
+Για 4 threads και $A = 10x10$:
+
+\includegraphics{res/run2.png} \\
+
+Για 3 threads και $A = 100x100$. Παρατηρούμε ότι το συγκεκριμένο τρέξιμο
+είχε δεδομένα τέτοια ώστε να μην πληρείται η προϋπόθεση του να είναι ο πίνακας
+αυστηρά διαγώνια δεσπόζων:
+
+\includegraphics[width=\textwidth]{res/run3.png} \\
+
+Στα παρακάτω τρεξίματα ο πίνακας θα είναι $1000x1000$, θα έχει τα ίδια
+στοιχεία, αλλά κάθε τρέξιμο θα έχει διαφορετικό αριθμό threads, ωστέ να
+παρατηρήσουμε τις διαφορές στην ταχύτητα εκτέλεσης του προγράμματος ανάλογα με
+τον αριθμό των threads.
+
+Παρατηρούμε ότι όταν τα threads είναι περισσότερα από 1, η ταχύτητα εκτέλεσης
+σχεδόν υποδιπλασιάζεται.
+
+Για 1 thread:
+
+\includegraphics[width=\textwidth]{res/run4.png} \\
+
+Για 2 threads:
+
+\includegraphics[width=\textwidth]{res/run5.png} \\
+
+Για 3 threads:
+
+\includegraphics[width=\textwidth]{res/run6.png} \\
+
+Για 4 threads:
+
+\includegraphics[width=\textwidth]{res/run7.png} \\
+
+\end{document}
diff --git a/c_parallel_systems/ex1/ex1.c b/c_parallel_systems/ex1/ex1.c
@@ -5,7 +5,29 @@
#include <omp.h>
-#define abs(x) ((x) < 0 ? -(x) : (x))
+#define abs(x) ((x) < 0 ? -(x) : (x))
+
+static void *emalloc(size_t);
+static int safe_input(const char *, ...);
+static void pretty_print(int **, int, const char *);
+static int strictly_diagonal_dominant(int **, int);
+static int diagonal_max(int **, int);
+static int **new_array(int **, int, int);
+static int calc_min(int **, int);
+
+/*
+ * Fail-safe malloc(3).
+ */
+static void *
+emalloc(size_t nb)
+{
+ void *p;
+
+ if ((p = malloc(nb)) == NULL)
+ err(1, "malloc");
+
+ return (p);
+}
static int
safe_input(const char *fmt, ...)
@@ -14,9 +36,16 @@ safe_input(const char *fmt, ...)
char buf[48];
int n, rc;
+ /* Collect the arguments into a buffer. */
va_start(args, fmt);
vsnprintf(buf, sizeof(buf), fmt, args);
va_end(args);
+
+ /*
+ * The following loop keeps asking for input as long as the current
+ * input wasn't correct. In this case "incorrect" input means anything
+ * other than digits.
+ */
do {
printf("\r%s", buf);
rc = scanf("%d", &n);
@@ -26,15 +55,28 @@ safe_input(const char *fmt, ...)
return (n);
}
-static void *
-emalloc(size_t nb)
+/*
+ * Print the contents of a 2D array like:
+ *
+ * array = [
+ * [x, y, z]
+ * [x, y, z]
+ * ]
+ */
+static void
+pretty_print(int **arr, int n, const char *name)
{
- void *p;
+ int i, j;
- if ((p = malloc(nb)) == NULL)
- err(1, "malloc");
-
- return (p);
+ printf("\n%s = [\n", name);
+ for (i = 0; i < n; i++) {
+ printf("\t[");
+ for (j = 0; j < n; j++) {
+ printf("%d%s", arr[i][j],
+ (j == n - 1) ? "]\n" : ", ");
+ }
+ }
+ printf("]\n");
}
static int
@@ -88,27 +130,44 @@ new_array(int **a, int m, int n)
}
static int
-min_reduction(int **b, int n)
+calc_min(int **b, int n)
{
- int i, min;
+ int i, j, min;
+ /* with reduction */
min = b[0][0];
#pragma omp parallel for reduction(min : min)
for (i = 0; i < n; i++) {
- if (b[i][i] < min)
- min = b[i][i];
+ for (j = 0; j < n; j++) {
+ if (b[i][j] < min)
+ min = b[i][j];
+ }
+ }
+
+ /* without reduction, with critical region protection */
+ min = b[0][0];
+#pragma omp parallel for private(i, j) shared(min)
+ for (i = 0; i < n; i++) {
+ for (j = 0; j < n; j++) {
+#pragma omp critical
+ {
+ if (b[i][j] < min)
+ min = b[i][j];
+ }
+ }
}
+ /* XXX: didn't implement binary tree method */
+
return (min);
}
-/* TODO: min_no_reduction() */
-
int
main(int argc, char *argv[])
{
int **a, **b;
int i, j, m, min, n, ntd;
+ double start, end;
ntd = safe_input("threads: ", 0);
omp_set_num_threads(ntd);
@@ -121,22 +180,25 @@ main(int argc, char *argv[])
a[i][j] = safe_input("a[%d][%d]: ", i, j);
}
+ start = omp_get_wtime();
+
if (strictly_diagonal_dominant(a, n)) {
m = diagonal_max(a, n);
- printf("diagonal_max: %d\n", m);
-
b = new_array(a, m, n);
+ min = calc_min(b, n);
- min = min_reduction(b, n);
- printf("min_reduction: %d\n", min);
+ pretty_print(a, n, "A");
+ pretty_print(b, n, "B");
+ printf("Diagonal max: %d\n", m);
+ printf("Min: %d\n", min);
- for (i = 0; i < n; i++)
- for (j = 0; j < n; j++)
- printf("b[%d][%d]: %d\n", i, j, b[i][j]);
free(b);
} else
printf("not strictly diagonal dominant\n");
+ end = omp_get_wtime();
+ printf("Total time: %f seconds\n", end - start);
+
free(a);
return (0);
diff --git a/c_parallel_systems/ex1/randinput b/c_parallel_systems/ex1/randinput
@@ -0,0 +1,12 @@
+#!/bin/sh
+
+usage()
+{
+ echo "usage: ${0##*/} nthreads N" 1>&2
+ exit 1
+}
+
+test ${#} -ne 2 && usage
+echo ${1}
+echo ${2}
+strings -n 1 < /dev/random | grep -o '[[:digit:]]' | head -n$((${2} * ${2}))
diff --git a/c_parallel_systems/ex1/res/run1.png b/c_parallel_systems/ex1/res/run1.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run2.png b/c_parallel_systems/ex1/res/run2.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run3.png b/c_parallel_systems/ex1/res/run3.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run4.png b/c_parallel_systems/ex1/res/run4.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run5.png b/c_parallel_systems/ex1/res/run5.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run6.png b/c_parallel_systems/ex1/res/run6.png
Binary files differ.
diff --git a/c_parallel_systems/ex1/res/run7.png b/c_parallel_systems/ex1/res/run7.png
Binary files differ.
