Matrix Multiplication

Στην αυτή την άσκηση θα εξοικειωθείτε με την χρήση των threads στην γλώσσα C στα πλαίσια της οποίας θα υλοποιήσετε ένα πρόγραμμα για τον πολλαπλασιασμό δύο πινάκων. Το πρόγραμμά σας θα αποτελείται από πολλά threads που θα εκτελούν τον πολλαπλασιασμό.

Τα threads ή διαφορετικά Light Weight Processes κοστίζουν λιγότερο στο σύστημα από ότι μια διεργασία, αφού μοιράζονται το ίδιο κομμάτι μνήμης με τη διεργασία που τα δημιούργησε. Έτσι, ενώ στην κλήση της fork το σύστημα πρέπει να δεσμεύσει μνήμη για την νέα διεργασία, στην περίπτωση των threads δεν ζητείται περισσότερη μνήμη από το λειτουργικό. Τα threads έχουν κοινό address space με την διεργασία που τα δημιούργησε και μοιράζονται εξ' ορισμού κοινές μεταβλητές. Aυτό είναι βολικό σε πολλές περιπτώσεις, αλλά ταυτόχρονα δημιουργούνται κάποια προβλήματα συγχρονισμού.

Αναλυτικότερα, το πρόγραμμά σας θα διαβάζει τους δύο πίνακες από δύο διαφορετικά αρχεία. Θα πρέπει να γίνεται έλεγχος στις διαστάσεις των πινάκων έτσι ώστε να είναι εφικτός ο πολλαπλασιασμός. Επιπλέον ο χρήστης θα ορίζει τον αριθμό των threads που θα δημιουργεί το πρόγραμμά μέσω παραμέτρου (command line argument). Στη συνέχεια η εφαρμογή θα δημιουργεί τον αντίστοιχο αριθμό threads τα οποία θα παίρνουν από μια γραμμή του πρώτου πίνακα και θα την πολλαπλασιάζουν με τις στήλες του δεύτερου πίνακα. Το αποτέλεσμα κάθε φορά θα αποθηκεύεται στην κατάλληλη θέση ενός τρίτου πίνακα στον οποίο θα "χτίζεται" το τελικό αποτέλεσμα. Προσοχή στα διάφορα θέματα συγχρονισμού. Τα threads πρέπει να αναλάβουν τον υπολογισμό διαφορετικών γραμμών του πρώτου πίνακα ώστε να μην υπολογίσουν τις ίδιες πράξεις. Σε κάθε βήμα το κάθε thread πρέπει να εκτυπώνει ποία γραμμή του πρώτου πίνακα έχει αναλάβει. Για αυτό το λόγο θα χρησιμοποιήσετε mutex.

Παράδειγμα πολλαπλασιασμού πινάκων

Γενικά ο πολλαπλασιασμός μεταξύ δυο πινάκων ορίζεται ως εξής: A x B = C όπου C[i, j] = εσωτερικό γινόμενο της i-οστής γραμμής του Α με την j-οστή στήλη του Β.

Οι πίνακες θα πρέπει να είναι της μορφής AxB και BxΓ ώστε να μπορεί να γίνει ο πολλαπλασιασμός. Το αποτέλεσμα θα είναι ένας πίνακας μεγέθους ΑxΓ.

Ζητούμενα της άσκησης

Ο αιθμός των threads που δημιουργούνται θα ορίζεται από το χρήστη μέσω παραμέτρου που θα δέχεται το πρόγραμμά σας. Επίσης οι αρχικοί πίνακες θα διαβάζονται από δύο διαφορετικά αρχεία που θα δίδονται ως είσοδος στο πρόγραμμά σας.

π.χ. ./a.out 3 matrix1 matrix2

Τα αρχεία που περιέχουν τους αρχικούς πίνακες θα έχουν την εξής δομή:

Στην πρώτη γραμμή θα αναγράφονται οι διαστάσεις του πίνακα (πρώτα αριθμός γραμμών και μετά αριθμός στηλών) και στις επόμενες γραμμές τα στοιχεία του πίνακα χωρισμένα ανα γραμμή, όπως φαίνεται στο παραπάνω παράδειγμα. Τα στοιχεία και οι διαστάσεις του πίνακα θα χωρίζονται μεταξύ τους με whitespaces.

Για παράδειγμα, αν έχουμε δύο πίνακες διάστασης 3x3 και ορίσουμε τη δημιουργία 2 threads, αυτά θα εργαστούν ως εξης:
Το 1ο thread θα πολλαπλασιάσει την 1η γραμμή του 1ου πίνακα με τις στήλες του 2ου πίνακα.
Το 2ο thread θα πολλαπλασιάσει την 2η γραμμή του 1ου πίνακα με τις στήλες του 2ου πίνακα.
Όποιο από τα 2 threads τελειώσει πρώτο, θα συνεχίσει την ίδια δουλειά με την επόμενη γραμμή του 1ου πίνακα.
Αυτό θα συνεχίζεται μέχρι να εξαντληθούν οι γραμμές του πρώτου πίνακα.

Προσοχή!
Πρέπει να αποκλείσετε το ενδεχόμενο υπολογισμού του γινομένου μιάς γραμμής του πρώτου πίνακα και από τα δύο ή περισσότερα threads χρησιμοποιώντας mutex . Σε κάθε περίπτωση το κάθε thread πρέπει να τυπώνει ποιά γραμμή έχει αναλάβει. Στο τέλος η κύρια διεργασία πρέπει να τυπώσει τον τελικό πίνακα του αποτελέσματος.

Reference - man pages

Ένα man page περιγράφει τον τρόπο λειτουργίας ενός προγράμματος, ενός system call ή μιας library function. Η εμφάνιση ενός man page γίνεται με τη χρήση της εντολής:

man(1)

Για να δείτε το man page (σε Linux) που αναφέρεται στη foo(N), κάνετε:

% man -S N foo

Ο συμβολισμός foo(N) αναφέρεται στο man page που περιγράφει τη foo στη κατηγορία (section) 'Ν'.

Λίστα με χρήσιμα man pages για την Aσκηση 3

Σας παραθέτουμε man pages με system calls και κάποιες συναρτήσεις που μπορεί να χρειαστείτε για την υλοποίηση της άσκησης. Η παρακάτω λίστα δεν είναι δεσμευτική. Μπορείτε να χρησιμοποιήσετε και εναλλακτικούς τρόπους.

Mutex
pthread_mutex_init()
pthread_mutex_destroy()
pthread_mutex_lock()
pthread_mutex_unlock()

POSIX Threads
pthread_create()
pthread_join()
pthread_setconcurrency()

Κάποιες από τις βιβλιοθήκες που θα πρέπει να χρησιμοποιήσετε είναι οι παρακάτω:
#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <unistd.h>


Κατά το compilation θα πρέπει να γίνει με την παράμετρο -pthread

Παρατηρήσεις

1. Η άσκηση είναι ατομική. Τυχόν αντιγραφές μπορούν να ανιχνευθούν εύκολα από κατάλληλο πρόγραμμα και θα μηδενιστούν. Συμπεριλάβετε το όνομα σας, τον αριθμό μητρώου σας, και το username σας σε όλα τα αρχεία.
2. Κατασκευάστε ένα αρχείο Makefile, έτσι ώστε πληκτρολογόντας make all να γίνεται η μεταγλώττιση (compilation) του προγράμματος και να παράγεται το εκτελέσιμο αρχείο. Επίσης πληκτρολογόντας make clean να καθαρίζονται όλα τα περιττά αρχεία, και να μένουν μόνο τα αρχεία που χρειάζονται για τη μεταγλώττιση.
3. Γράψτε ένα αρχείο README, το πολυ 30 γραμμών, με επεξηγήσεις για τον τρόπο υλοποίησης.
4. Τοποθετήστε σε ένα κατάλογο όλα τα αρχεία που χρειάζονται για την άσκηση 3. Παραδώστε τα παραπάνω αρχεία χρησιμοποιώντας το πρόγραμμα submit (πληκτρολογήστε submit assignment_3@hy345 directory_name από τον κατάλογο που περιέχει τον κατάλογο directory_name με τα αρχέια της άσκησης).
5. Σε πολλές περιπτώσεις τα ονόματα των συναρτήσεων βιβλιοθήκης είναι ενδεικτικά. Μπορείτε να χρησιμοποιήσετε όποια σας βολεύουν.