Cilk

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

Σχεδίαση

Η βασική αρχή πίσω από τη σχεδίαση της γλώσσας Cilk είναι ότι ο προγραμματιστής είναι υπεύθυνος όσον αφορά την έκθεση του παραλληλισμού που υπάρχει σε ένα πρόγραμμα, εντοπίζοντας ποια στοιχεία μπορούν να εκτελεστούν παράλληλα με ασφάλεια - τότε είναι το περιβάλλον χρόνου εκτέλεσης, και ειδικότερα ο χρονοπρογραμματιστής (scheduler), που αποφασίζει κατά τη διάρκεια της εκτέλεσης πώς να μοιράσει τις εργασίες στους επεξεργαστές. Λόγω αυτού του διαχωρισμού αρμοδιοτήτων, ένα πρόγραμμα Cilk μπορεί να εκτελείται χωρίς μετατροπή σε οποιοδήποτε αριθμό επεξεργαστών, ακόμα και σε ένα μόνο επεξεργαστή.

Η γλώσσα Cilk αναπτύσσεται από το 1994 στο Εργαστήριο Επιστήμης Υπολογιστών (Laboratory for Computer Science) του MIT. Βασίζεται στην ANSI C, με την προσθήκη κάποιων ειδικών λέξεων-κλειδιών. Όταν αυτές οι λέξεις-κλειδιά της Cilk αφαιρεθούν από πηγαίο κώδικα σε Cilk, το αποτέλεσμα είναι ένα έγκυρο πρόγραμμα C, που αποκαλείται η σειριακή έκθλιψη (serial elision ή C elision) της πλήρους προγράμματος σε Cilk. Η Cilk είναι γνήσια επέκταση της C και η σειριακή έκθλιψη οποιουδήποτε προγράμματος σε Cilk είναι πάντα έγκυρη υλοποίηση σε C της σημασιολογίας του παράλληλου προγράμματος σε Cilk. Παρά τις ομοιότητες, η Cilk δεν έχει απευθείας σχέση με την Concurrent C των Bell Labs της AT&T.

Η Cilk++ είναι μια εμπορική έκδοση της Cilk (από την Cilk Arts, Inc.) που υποστηρίζει τη C και την C++ ενώ είναι συμβατή με τους μεταγλωττιστές GCC και Microsoft C++. Υπάρχουν εκδόσεις της για ακαδημαϊκή χρήση και σε μορφή ανοιχτού κώδικα (με μια ειδική άδεια λογισμικού μεταξύ της ανανεωμένης άδειας BSD και της LGPL). Ο αρχικός κώδικας της Cilk εξακολουθεί να είναι διαθέσιμος από το MIT. Τον Ιούλιο του 2009, η Intel αγόρασε την Cilk Arts, την τεχνολογία της Cilk++ και το εμπορικό σήμα Cilk. Το 2010 η Intel κυκλοφόρησε μια εμπορική υλοποίηση των μεταγλωττιστών της σε συνδυασμό με κάποιες δομές παραλληλισμού δεδομένων, με το όνομα Intel Cilk Plus. Η Intel έχει επίσης κυκλοφορήσει προδιαγραφές για χρήση από άλλες συμβατές υλοποιήσεις, με το λογότυπο να μπορούν να το χρησιμοποιήσουν όσες συμμορφώνονται με τις προδιαγραφές.

Στην αρχική υλοποίηση της Cilk του MIT, η πρώτη λέξη-κλειδί της Cilk είναι στην πραγματικότητα η cilk, που σημειώνει μια συνάρτηση που είναι γραμμένη σε Cilk. Επειδή οι διαδικασίες της Cilk μπορούν να καλούν απευθείας διαδικασίες της C, αλλά οι διαδικασίες της C δε μπορούν να καλούν απευθείας ή να δημιουργούν σε νέο νήμα (spawn) διαδικασίες της Cilk, η παραπάνω λέξη-κλειδί χρειάζεται για να διακρίνεται ο κώδικας σε Cilk από τον κώδικα σε C.

Οι υπόλοιπες λέξεις-κλειδιά είναι:

• spawn
• sync
• inlet
• abort

και περιγράφονται στη συνέχεια.

Βασικός παραλληλισμός με τη 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, και η γλώσσα να υλοποιηθεί από άλλους μεταγλωττιστές ώστε να υιοθετηθεί στη βιομηχανία λογισμικού.

Δείτε επίσης

• Παράλληλος προγραμματισμός
• Intel Threading Building Blocks

Δημοσιεύσεις

• Cilk: An Efficient Multithreaded Runtime System των Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, και Yuli Zhou. Proceedings of the Fifth ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming (PPoPP), pp. 207–216, 1995.

Εξωτερικοί σύνδεσμοι

• Cilk: Φιλοσοφία και Χρήση, Παράλληλα Συστήματα Επεξεργασίας, ΕΜΠ
• Η σελίδα του Cilk Project στο MIT (Αγγλικά)
• Cilk Arts, Inc. (Αγγλικά)
• Cilk++ Technology Overview (Αγγλικά)
• Cilk++ Product Demonstration (Αγγλικά)
• Multicore Programming blog (Αγγλικά)
• e-Book για τον προγραμματισμό με πολλούς πυρήνες (Multicore Programming), εξηγεί ανοιχτά προβλήματα και τις τελευταίες τεχνικές για την αντιμτωπισή τους. (Αγγλικά)