Cilk

Η Cilk είναι μια γλώσσα προγραμματισμού γενικών καθηκόντων, σχεδιασμένη για πολυνηματικούς παράλληλους υπολογισμούς (multithreaded parallel computing). Εμπορικά είναι διαθέσιμη σαν Intel Cilk Plus.

Βασικός παραλληλισμός με τη Cilk

Δύο λέξεις-κλειδιά χρειάζονται μόνο για να χρησιμοποιήσει κανείς τα παράλληλα χαρακτηριστικά της Cilk:
spawn -- δηλώνει ότι μια κλήση διαδικασίας μπορεί να εκτελεστεί με ασφάλεια παράλληλα με άλλο εκτελούμενο κώδικα. Ο χρονοπρογραμματιστής δεν είναι υποχρεωμένος να εκτελέσει αυτήν τη διαδικασία παράλληλα με τον υπόλοιπο κώδικα - απλά η λέξη κλειδί τον ενημερώνει ότι έχει την ικανότητα να το κάνει.
sync -- δηλώνει ότι η εκτέλεση της τρέχουσας διαδικασίας δε μπορεί να προχωρήσει μέχρι όλες οι προηγούμενες διαδικασίες που έτρεξαν παράλληλα να έχουν τερματίσει και να έχουν επιστρέψει τα αποτελέσματά τους στο πατρικό πλαίσιο (frame). Αποτελεί παράδειγμα μεθόδου "συνόρου" ("barrier").

Παράδειγμα κώδικα

Ακολουθεί μια αναδρομική υλοποίηση της συνάρτησης Φιμπονάτσι σε Cilk, με παράλληλες αναδρομικές κλήσεις, που δείχνει τη χρήση των λέξεων-κλειδιών cilk, spawn και sync. (Ο κώδικας σε Cilk δεν έχει αριθμούς, οι παρακάτω αριθμοί προστέθηκαν για ευκολία στην εξήγηση που ακολουθεί.)
01 cilk int fib (int n)
02 {
03     if (n < 2) return n;
04     else
05     {
06        int x, y;
07  
08        x = spawn fib (n-1);
09        y = spawn fib (n-2);
10  
11        sync;
12  
13        return (x+y);
14     }
15 }
Αν ο παραπάνω κώδικας εκτελεστεί από έναν επεξεργαστή για να υπολογιστεί η τιμή της fib(2), ο επεξεργαστής θα δημιουργούσε ένα πλαίσιο για την fib(2), και θα εκτελούσε τις γραμμές 01 έως 05. Στη γραμμή 06 θα κρατούσε χώρο στο πλαίσιο για να κρατήσει τις τιμές των x και y. Στη γραμμή 08 ο επεξεργαστής θα έπρεπε να σταματήσει το τρέχον πλαίσιο, να δημιουργήσει ένα νέο πλαίσιο για να εκτελέσει τη διαδικασία fib(1), να εκτελέσει τον κώδικα αυτού του πλαισίου μέχρι να βρει μια εντολή return και τότε να συνεχίσει την εκτέλεση του πλαισίου της fib(2) με την τιμή της fib(1) να τοποθετείται στη μεταβλητή x της fib(2). Στην επόμενη γραμμή, θα έπρεπε να σταματήσει πάλι, για να εκτελέσει την fib(0) και να τοποθετήσει το αποτέλεσμά της στη μεταβλητή y της fib(2).
Όταν όμως ο κώδικας εκτελεστεί σε έναν υπολογιστή με πολλούς επεξεργαστές (multiprocessor), η εκτέλεση γίνεται διαφορετικά. Ο ένας επεξεργαστής αρχίζει την εκτέλεση της fib(2): όταν φτάσει στη γραμμή 08, η λέξη-κλειδί spawn της κλήσης fib(n-1) πληροφορεί τον επεξεργαστή ότι μπορεί με ασφάλεια να δώσει αυτήν τη νέα εργασία (job) σε κάποιον άλλο επεξεργαστή, ο οποίος μπορεί να δημιουργήσει ένα πλαίσιο για τη fib(1), να εκτελέσει τον κώδικά της, και να αποθηκεύσει το αποτέλεσμα στο πλαίσιο της fib(2) όταν τερματίσει - ο πρώτος επεξεργαστής συνεχίζει να εκτελεί τον κώδικα της fib(2) αυτό το χρονικό διάστημα. Ένας επεξεργαστής δεν είναι υποχρεωμένος να δώσει μια διαδικασία προς παράλληλη εκτέλεση κάπου αλλού - αν ο υπολογιστής έχει μόνο δύο επεξεργαστές και ο δεύτερος είναι απασχολημένος να εκτελεί τη fib(1) όταν ο επεξεργαστής που εκτελεί τη fib(2) φτάσει στην κλήση της διαδικασίας, ο πρώτος επεξεργαστής θα σταματήσει τη fib(2) και θα εκτελέσει τη fib(0), σαν να ήταν ο μοναδικός επεξεργαστής. Αν κάποιος άλλος επεξεργαστής είναι διαθέσιμος, φυσικά θα χρησιμοποιηθεί, και οι τρεις επεξεργαστές θα εκτελούν ταυτόχρονα διαφορετικά πλαίσια.
Αν ο επεξεργαστής που εκτελεί τη fib(2) εκτελούσε τη γραμμή 13 πριν οι άλλες δύο διαδικασίες είχαν ολοκληρώσει τα πλαίσιά τους, θα προέκυπτε λάθος αποτέλεσμα ή σφάλμα εκτέλεσης: η fib(2) θα προσπαθούσε να προσθέσει τις τιμές που είναι αποθηκευμένες στη x και στην y, αλλά η μία (ή και οι δύο) από αυτές τις τιμές θα έλειπε. Αυτός είναι ο σκοπός της λέξης-κλειδί sync που φαίνεται στη γραμμή 11: λέει στον επεξεργαστή που εκτελεί το πλαίσιο ότι πρέπει να σταματήσει την εκτέλεσή του, μέχρι όλες οι κλήσεις διαδικασίας που έχει δημιουργήσει για παράλληλη εκτέλεση, να έχουν επιστρέψει. Όταν η fib(2) μπορεί να περάσει την εντολή sync στη γραμμή 11, τότε η fib(1) και η fib(0) θα έχουν τερματίσει και θα έχουν τοποθετήσει τα αποτελέσματά τους στη x και στην y, επομένως θα είναι ασφαλές να γίνουν υπολογισμοί με αυτές τις μεταβλητές.

Προχωρημένος παραλληλισμός με τη Cilk: Inlets

Οι δύο λέξεις-κλειδιά της Cilk που μένουν είναι λίγο πιο προχωρημένες και έχουν να κάνουν με τις εισόδους (inlets). Συνήθως, όταν μια διαδικασία σε Cilk κληθεί να εκτελεστεί παράλληλα με άλλο κώδικα, μπορεί να επιστρέψει τα αποτελέσματά της στη γονική διαδικασία μόνο βάζοντάς τα σε μια μεταβλητή στο πλαίσιο του γονέα, όπως ακριβώς οι μεταβλητές x and y στα παραδείγματα που αναφέρθηκαν προηγουμένως.
Η εναλλακτική λύση είναι να χρησιμοποιηθεί ένα inlet, που είναι μια εσωτερική συνάρτηση μιας διαδικασίας Cilk, η οποία χειρίζεται τα αποτελέσματα που επιστρέφει μια διαδικασία που εκτελέστηκε παράλληλα. Ένας βασικός λόγος υπέρ της χρήσης inlets είναι ότι όλα τα inlets μιας διαδικασίας εγγυημένα λειτουργούν ατομικά (δηλ. χωρίς να επηρεάζουν το ένα το άλλο, ούτε τη γονική διαδικασία), αποφεύγοντας σφάλματα που θα μπορούσαν να συμβούν αν οι διαδικασίες που επιστρέφουν προσπαθούσαν να τροποποιήσουν τις ίδιες μεταβλητές στο γονικό πλαίσιο την ίδια στιγμή.
inlet -- δηλώνει ότι μια συνάρτηση που ορίζεται μέσα σε μια διαδικασία είναι inlet.
abort -- μπορεί να χρησιμοποιηθεί μόνο μέσα σε ένα inlet - πληροφορεί το χρονοπρογραμματιστή ότι όλες οι άλλες διαδικασίες που έχουν δοθεί προς παράλληλη εκτέλεση από τη γονική διαδικασία μπορούν να ακυρωθούν με ασφάλεια.

Work-stealing

Ο χρονοπρογραμματιστής της Cilk χρησιμοποιεί μια αρχή που ονομάζεται "κλοπή εργασίας" ("work-stealing") για να διαιρεί την εκτέλεση των διαδικασιών ανάμεσα σε πολλούς επεξεργαστές.
Έστω η περίπτωση της εκτέλεσης κώδικα Cilk σε έναν υπολογιστή με έναν επεξεργαστή. Ο επεξεργαστής έχει μια στοίβα κλήσεων, στην οποία τοποθετεί κάθε πλαίσιο που πρέπει να σταματήσει για να καλέσει μια διαδικασία. Αν εκτελεί τη fib(2) και συναντήσει μια αναδρομική κλήση στη fib(1), θα αποθηκεύσει την κατάσταση της fib(2), μαζί με τις μεταβλητές της και το σημείο που σταμάτησε η εκτέλεση του κώδικα, και θα τοποθετήσει αυτήν την κατάσταση στη στοίβα. Δεν πρόκειται να αφαιρέσει μια σταματημένη κατάσταση από τη στοίβα και να τη συνεχίσει, παρά μόνο όταν η διαδικασία στην οποία οφείλεται αυτό και όλες οι διαδικασίες που κάλεσε, έχουν εκτελεστεί πλήρως.
Στην περίπτωση πολλών επεξεργαστών, τα πράγματα αλλάζουν. Κάθε επεξεργαστής έχει μια στοίβα για την αποθήκευση πλαισίων, των οποίων η εκτέλεση έχει σταματήσει - οι στοίβες όμως αυτές μοιάζουν με διπλές ουρές (deques), επειδή σταματημένες καταστάσεις μπορούν να αφαιρούνται και από τα δύο άκρα. Ένας επεξεργαστής μπορεί να αφαιρεί καταστάσεις από τη δική του στοίβα από το ίδιο άκρο, στο οποίο τις προσθέτει, ένας άλλος επεξεργαστής όμως που δεν εργάζεται (που έχει τελειώσει τις εργασίες του ή δεν του έχει δοθεί κάποια εργασία) θα επιλέξει κάποιον άλλο επεξεργαστή τυχαία, μέσω του χρονοπρογραμματιστή, και θα προσπαθήσει να "κλέψει" κάποια εργασία από το άλλο άκρο των σταματημένων καταστάσεων στη στοίβα, την οποία εργασία στην συνέχεια μπορεί να εκτελέσει. Οι καταστάσεις που κλέβει είναι αυτές που ο αρχικός επεξεργαστής θα εκτελούσε τελευταίες.

Εμπορική παρουσία

Πριν το ~2006, η Cilk περιοριζόταν στην αγορά των συστημάτων επεξεργασίας υψηλής απόδοσης (high-performance computing). Η εμφάνιση των πολυπύρηνων επεξεργαστών στους κοινούς υπολογιστές όμως σημαίνει πια ότι κάθε χρόνο κυκλοφορούν εκατοντάδες εκατομμυρίων παράλληλων υπολογιστών. Δημιουργήθηκε τότε η Cilk Arts για να εκμεταλλευτεί αυτήν την ευκαιρία: το 2006, ο καθηγητής Charles Leiserson ξεκίνησε τη Cilk Arts για να δημιουργήσει και να κυκλοφορήσει στην αγορά μια σύγχρονη έκδοση της Cilk που να υποστηρίζει τις εμπορικές ανάγκες της επόμενης γενιάς των προγραμματιστών. Η εταιρεία έλαβε χρηματοδότηση τον Οκτώβριο του 2007 και η Cilk++ 1.0 εμφανίστηκε στην αγορά το Δεκέμβριο του 2008. Η διαφορές της Cilk++ σε σχέση με τη Cilk είναι αρκετές: υποστηρίζει τη C++, λειτουργεί και με τους μεταγλωττιστές της Microsoft και με τον GCC, υποστηρίζει βρόχους επανάληψης (loops) και περιλαμβάνει τα "υπεραντικείμενα Cilk" ("Cilk hyperobjects") - μια νέα δομή που σχεδιάστηκε για να λύνει προβλήματα (τύπου "data race") που δημιουργούνται από την παράλληλη πρόσβαση σε καθολικές μεταβλητές.
Στις 31 Ιουλίου του 2009, η Cilk Arts ανακοίνωσε στη σελίδα της ότι τα προϊόντα της και η ομάδα των μηχανικών της ανήκαν πια στην Intel. Η Intel και η Cilk Arts ενώθηκαν και προχώρησαν την τεχνολογία ακόμα περισσότερο, με αποτέλεσμα την κυκλοφορία της Intel Cilk Plus το Σεπτέμβριο του 2010. Η Intel Cilk Plus υιοθετεί κάποιες απλοποιήσεις, που προτάθηκαν από τη Cilk Arts για τη Cilk++, ώστε κάποιες από τις λέξεις-κλειδιά της αρχικής Cilk να μη χρειάζονται, ενώ πρόσθεσε τη δυνατότητα να εκτελούνται παράλληλα συναρτήσεις και να γίνεται χειρισμός μεταβλητών που χρησιμοποιούνται σε λειτουργίες αναγωγής (reduction). Η Intel Cilk Plus διαφέρει από τη Cilk και τη Cilk++: περιλαμβάνει επεκτάσεις για πίνακες (arrays), περιλαμβάνεται σε έναν εμπορικό μεταγλωττιστή (της Intel) και είναι συμβατή με τους αποσφαλματωτές που ήδη υπάρχουν.
Η Intel έχει δηλώσει ότι θέλει να επεξεργαστεί και να αναπτύξει τη Cilk Plus, και η γλώσσα να υλοποιηθεί από άλλους μεταγλωττιστές ώστε να υιοθετηθεί στη βιομηχανία λογισμικού.