Η πορεία των πρωτότυπων επιστημονικών θεωριών και ιδεών του Γκλουσκόφ και της σχολής του και οι καινοτόμες τεχνολογικές εφαρμογές τους

(Απόσπασμα από το Ivan V. Sergienko, Topical Directions of Informatics. In Memory of V. M. Glushkov, εκδ. Springer, New York, 2014).

Του Ivan V. Sergienko, Ινστιτούτο Κυβερνητικής Β. Μ. Γκλουσκόφ της Εθνικής Ακαδημίας Επιστημών της Ουκρανίας, Κίεβο, Ουκρανία (πρώην Ινστιτούτο Κυβερνητικής της Ακαδημίας Επιστημών της Ουκρανικής Σοβιετικής Σοσιαλιστικής Δημοκρατίας).

Μετάφραση: Αντώνης Ευθυμιάτος, φοιτητής Ηλεκτρολόγος Μηχανικός στο Πανεπιστήμιο Πατρών.

Ο Β. Μ. Γκλουσκόφ και η σχολή του έχουν σημαντική συμβολή στη διαμόρφωση και την ανάπτυξη της επιστήμης του προγραμματισμού παγκοσμίως, θεωρητικής και εφαρμοσμένης. Σε αντίθεση με πολλές άλλες ομάδες και σχολές που εξέτασαν τον προγραμματισμό με τη στενή έννοια, π.χ. τις γλώσσες προγραμματισμού, τους μεταγλωττιστές, και τη μεθοδολογία [χειρισμούς, τεχνικές], η σχολή του Γκλουσκόφ εξέτασε τα ζητήματα του προγραμματισμού σε ένα πολύ ευρύτερο πλαίσιο. Το πλαίσιο αυτό περιλάμβανε την αρχιτεκτονική των υπολογιστικών συστημάτων, την από κοινού [διαρθρωμένη] ανάπτυξη λογισμικού και υλικού για υπολογιστικά συστήματα και την ενίσχυση της νοημοσύνης του εσωτερικού και του εξωτερικού λογισμικού.

Και όλα ξεκίνησαν με τη θεωρία των αυτόματων. Όταν ο Β. Μ. Γκλουσκόφ, ένας εξαιρετικός αλγεβριστής γνωστός για τα έργα του πάνω στο 5ο πρόβλημα του Χίλμπερτ (Hilbert), άλλαξε ξαφνικά την κατεύθυνση της δραστηριότητάς του και ηγήθηκε του εργαστηρίου αριθμητικών μαθηματικών και τεχνολογίας υπολογιστών το 1956, ξεκίνησε με τον καθορισμό των βραχυπρόθεσμων και μακροπρόθεσμων στόχων στην ανάπτυξη της πληροφορικής ως νέας επιστήμης  (ενώ ήταν κυβερνητική με την ευρεία έννοια, η οποία κάλυπτε όλα όσα σχετίζονταν με την τεχνολογία υπολογιστών και τις εφαρμογές της). Γνώριζε πολύ καλά ότι η ανάπτυξη των υπολογιστών, του προγραμματισμού υπολογιστών και εφαρμογών απαιτούσε ένα νέο πεδίο θεμελιώδους γνώσης, το οποίο θα βασίζεται στο στέρεο θεμέλιο των σύγχρονων μαθηματικών. Έτσι, η δημιουργία και η ανάπτυξη της θεωρίας των αυτόματων έγινε ένας από τους άμεσους στόχους της δραστηριότητάς του.

Τα σημαντικότερα έργα του Γκλουσκόφ για τη θεωρία των αυτόματων χρονολογούνται το διάστημα 1959-1960. Ασχολήθηκε με δύο τομείς. Ο ένας προοριζόταν για τους μαθηματικούς. Μελετούσε τη θεωρία των αφηρημένων αυτόματων ως μαθηματική θεωρία που χρησιμοποιεί αφηρημένες αλγεβρικές δομές. Επινοήθηκαν οι αρχικοί αλγόριθμοι ανάλυσης και σύνθεσης πεπερασμένων αυτόματων (ο αλγόριθμος της σύνθεσης βασίστηκε στην έννοια που αργότερα έγινε γνωστή ως αυτόματο Glushkov). Καθιερώθηκαν οι σχέσεις με τα γνωστά μαθηματικά προβλήματα (όπως το πρόβλημα Burnside), αναπτύχθηκαν τα θεμέλια της θεωρίας των ομάδων και ημι-ομάδων (semigroup) αυτόματων κ.ο.κ. Ο άλλος τομέας προοριζόταν για μαθηματικούς ειδικευμένους στα εφαρμοσμένα μαθηματικά, μηχανικούς και προγραμματιστές υπολογιστών. Το 1962, δημοσιεύτηκε η μονογραφία του Γκλουσκόφ Η Σύνθεση των Ψηφιακών Αυτόματων. Αυτή η μονογραφία διαδραμάτισε ρόλο κλειδί στην εκλαΐκευση των τυπικών μεθόδων μεταξύ των μηχανικών σχεδίασης και στη βελτίωση της μαθηματικής τους παιδείας. Αρκετές γενιές ειδικών στην τεχνολογία υπολογιστών έμαθαν από αυτό το βιβλίο. Το 1964, ο Γκλουσκόφ τιμήθηκε με το βραβείο Λένιν για τα έργα του στη θεωρία των αυτόματων.

Ένα σεμινάριο για τη θεωρία των αυτόματων, το οποίο διεξαγόταν από το 1959 έπαιξε σημαντικό ρόλο στην ανάπτυξη αυτής της θεωρίας. Οι Yu. V. Kapitonova, O. A. Letichevskii, V. G. Bodnarchuk, V. N. Redko, P. I. Andon και οι άλλοι μαθητές του Γκλουσκόφ ήταν οι κύριοι συμμετέχοντες στο σεμινάριο. Αργότερα, καθένας από αυτούς ίδρυσε ένα ξεχωριστό πεδίο, αναπτύσσοντας και βελτιώνοντας αυτόματες-αλγεβρικές μεθόδους σε θεωρητικούς και εφαρμοσμένους τομείς της επιστήμης των υπολογιστών, συμπεριλαμβανομένου του προγραμματισμού.

Οι υπολογιστές της σειράς MIR

Μια ομάδα νέων επιστημόνων με επικεφαλής τον Γκλουσκόφ ασχολήθηκε όχι μόνο με θεωρητικά προβλήματα αλλά και με εφαρμογές της θεωρίας των αυτόματων, η οποία ήταν ακόμα σε πρώιμο στάδιο της ανάπτυξής της. Όλοι οι σημαντικοί αλγόριθμοι της τεχνολογίας σχεδίασης ηλεκτρονικών κυκλωμάτων που βασίζονται στη θεωρία πεπερασμένων αυτόματων εφαρμόστηκαν στον υπολογιστή "Κίεβο" (“Kyiv”) και αποτέλεσαν τη βάση του «Μικρού συστήματος αυτοματοποίησης της σύνθεσης των ψηφιακών αυτόματων». Το επόμενο βήμα στην εφαρμογή της θεωρίας των αυτόματων πίστευαν ότι θα ήταν ένας υπολογιστής MIR (μηχανή για υπολογισμούς μηχανικής).

Το σχέδιο της πρώτης μηχανής, που έβαλε τη βάση για τη μελλοντική σειρά μικρών υπολογιστών MIR, ήταν μοναδικό στην ουσία του. Συνδύαζε αρκετές ιδέες που διατυπώθηκαν από τον ιδιοφυή δημιουργός τους, τον Γκλουσκόφ. Η πρώτη ιδέα ήταν να συντεθεί ηλεκτρονική αριθμομηχανή θεωρούμενη ως ένα ψηφιακό αυτόματο, η οποία να μπορεί όχι μόνο να εκτελέσει αριθμητικές πράξεις, αλλά και να υπολογίζει ολοκληρώματα, να λύνει (αριθμητικά) διαφορικές εξισώσεις κ.λπ. Μόλις έγινε καθαρό ότι θα πρέπει να σχεδιαστεί υπολογιστής με επαρκώς αναπτυγμένη γλώσσα εισόδου, η πρώτη ιδέα συμπληρώθηκε με την ιδέα της διερμηνείας του υλικού (hardware interpretation) της γλώσσας προγραμματισμού υψηλού επιπέδου που είχε ήδη δοκιμαστεί στον υπολογιστή "Ουκρανία". Έτσι, η κατανόηση μιας γλώσσας υψηλού επιπέδου από το υλικό έγινε αντιληπτή ως ένας τρόπος ενίσχυσης της εσωτερικής νοημοσύνης του υπολογιστή.

Η πηγαία γλώσσα (source language) των πρώτων υπολογιστών MIR επικεντρώθηκε στις αριθμητικές μεθόδους για την επίλυση επιστημονικών και τεχνικών προβλημάτων. Γι’ αυτό, περιλάμβανε προτυποποιημένα μέσα προστακτικού προγραμματισμού (imperative programming)[1] τυπικά για την Algol ή την Fortran, αλλά ταυτόχρονα επέτρεψε τη χρήση πεπερασμένων και άπειρων σειρών και γινομένων, καθώς και αριθμητικές εκφράσεις με ολοκληρώματα. Υποστηρίζονταν επίσης αναδρομικοί ορισμοί συναρτήσεων. Με δεδομένο ότι το υλικό διερμήνευε τη γλώσσα, ήταν δυνατό να χρησιμοποιηθούν αριθμοί αυθαίρετου μήκους, οι οποίοι θα μπορούσαν να οριστούν μέσα στα προγράμματα. Προέβλεπε επίσης μια διαδραστική λειτουργία με τη χρήση μιας οθόνης, η οποία ήταν νέα για την τεχνολογία υπολογιστών της εποχής, και εύχρηστη απεικόνιση των αποτελεσμάτων των υπολογισμών με τη μορφή πινάκων και γραφημάτων.

Το επόμενο βήμα ήταν ο εμπλουτισμός της γλώσσας εισόδου με την ικανότητα να δουλεύει όχι μόνο με αριθμούς, αλλά και με μαθηματικές εκφράσεις και τύπους. Η γλώσσα ANALITIK ήταν μια από τις πρώτες γλώσσες της άλγεβρας υπολογιστών. Έχοντας τα προηγμένα μέσα χειρισμού συμβολικών πληροφοριών, χρησιμοποίησε (για πρώτη φορά) το μετασχηματισμό αλγεβρικών εκφράσεων ξαναγράφοντας τα συστήματα κανόνων στη σημασιολογικά σύνθετη άλγεβρα (semantically complex algebra), η οποία περιλάμβανε σχεδόν όλες τις βασικές λειτουργίες της μαθηματικής ανάλυσης συμπεριλαμβανόμενης ακόμη και της συμβολικής ολοκλήρωσης αναλυτικών εκφράσεων.

Η ANALITIK ήταν γνωστή στην παγκόσμια επιστημονική κοινότητα  και επηρέασε την περαιτέρω ανάπτυξη της άλγεβρας υπολογιστών. Το 1968, η ομάδα που ανέπτυξε τους υπολογιστές MIR βραβεύτηκε με το Κρατικό Βραβείο της ΕΣΣΔ.

Διακριτοί επεξεργαστές

Παρόλο που στη σχεδίαση του εσωτερικού λογισμικού του υπολογιστή MIR χρησιμοποιήθηκαν θεωρητικές μέθοδοι με αυτόματα, η αρχική ιδέα του Γκλουσκόφ να αναπαραστήσει τον υπολογιστή ως σύνθεση ενός μικρού αριθμού πεπερασμένων αυτόματων και να εφαρμόσει τυπικές μεθόδους σύνθεσης σ’ αυτά απέτυχε να εφαρμοστεί. Ο λόγος ήταν ότι οι μέθοδοι σύνθεσης πεπερασμένων αυτόματων βασίζονται σε αλγόριθμους που απαιτούν κάθε κατάσταση και κάθε σύμβολο εισόδου του αυτόματου να θεωρούνται ξεχωριστά. Αν, ωστόσο, η συσκευή έχει πολλούς καταχωρητές (registers), ο αριθμός των καταστάσεων εξαρτάται εκθετικά από τον αριθμό των bit πολλαπλασιασμένο με τον αριθμό των καταχωρητών. Γι’ αυτό, για την αλγοριθμική υποστήριξη της ανάπτυξης τέτοιων συσκευών, έπρεπε να βρεθεί μια άλλη προσέγγιση που θα τυποποιούσε την αρχιτεκτονική και τα αλγοριθμικά στάδια της σχεδίασης του υπολογιστή.

Ο Γκλουσκόφ πρότεινε μια τέτοια προσέγγιση το 1965 στις δημοσιεύσεις του «Θεωρία αυτόματων και ζητήματα δομικής σχεδίασης των υπολογιστών» και «Θεωρία αυτόματων και τυπικοί μετασχηματισμοί των μικρο-προγραμμάτων». Η πρώτη πρότεινε να μοντελοποιηθεί [μαθηματικοποιηθεί] ο υπολογιστής ως ένα αυτόματο ελέγχου και ένα αυτόματο πράξεων που αλληλεπιδρούν. Το αυτόματο πράξεων (operation automaton) ορίστηκε ως ένα σύνολο πεπερασμένων ή άπειρων καταχωρητών με περιοδικά ορισμένους μετασχηματισμούς, π.χ. μετασχηματισμούς που ορίζονται από εξισώσεις της μορφής , ή συστήματα παρόμοιων εξισώσεων, όπου το  είναι το i-στο ψηφίο του καταχωρητή  και το  είναι η νέα τιμή αυτού του ψηφίου. Η τοπική συμπεριφορά του μετασχηματισμού και η περιοδικότητά του σε σχέση με τα ψηφία καθιστούν αυτό τον ορισμό κοντινό σε δομές που χρησιμοποιούνται στην πράξη. Η χρησιμοποίηση του νέου μοντέλου επέτρεψε τη διαμόρφωση και την εξεύρεση λύσεων σε νέα προβλήματα που δε θα μπορούσαν να λυθούν με τη θεωρία των πεπερασμένων αυτόματων. Η δεύτερη δημοσίευση σηματοδότησε την αρχή ενός νέου πεδίου στη θεωρητική κυβερνητική: τη θεωρία των τυπικών μετασχηματισμών των προγραμμάτων και μικροπρογραμμάτων που βασίζονται στην άλγεβρα των αλγορίθμων.

Η σύνθεση των δύο αλληλεπιδρώντων αυτόματων θεωρήθηκε από τον Γκλουσκόφ ως ειδική περίπτωση της γενικής έννοιας του διακριτού επεξεργαστή, η οποία διερευνήθηκε αργότερα στα έργα του Γκλουσκόφ και των μαθητών του. Οι μελέτες αυτές έχουν εξελιχθεί προς δύο κατευθύνσεις. Μια κατεύθυνση αφορούσε την ανάλυση αφηρημένων αλγεβρικών προβλημάτων όπως η αναγνώριση της ισοδυναμίας, η βελτιστοποίηση του χρόνου εκτέλεσης, η μελέτη των σχέσεων ημι-ομάδων (semigroups) κ.λπ. Η άλλη κατεύθυνση ήταν η ανάπτυξη εφαρμοσμένων συστημάτων αυτοματοποιημένης σχεδίασης υπολογιστών, γλωσσών για την περιγραφή λειτουργικών αλγορίθμων συσκευών και μεθόδων και αλγορίθμων σχεδίασης υπολογιστών. Στη δεκαετία του 1970, αναπτύχθηκε το σύστημα PROEKT για την αυτόματη σχεδίαση υπολογιστών μαζί με το λογισμικό του. Η θεωρητική βάση αυτού του συστήματος ήταν η θεωρία των διακριτών επεξεργαστών και η άλγεβρα των αλγορίθμων.

Άλγεβρα αλγορίθμων

Το 1965, ο Γκλουσκόφ ονόμαζε άλγεβρα μικροπρογραμματισμού ή χρησιμοποιούσε τον όρο σύστημα αλγοριθμικής άλγεβρας (System of Algorithmic Algebras, SSA) για την άλγεβρα αλγορίθμων. Μια άλγεβρα αλγορίθμων είναι μια άλγεβρα δύο ειδών. Αποτελείται από την άλγεβρα των τελεστών και την άλγεβρα των συνθηκών (algebra of conditions). Οι τελεστές είναι μερικοί μετασχηματισμοί του συνόλου καταστάσεων δεδομένων (data states) (συνήθως καταστάσεις της μνήμης του προγράμματος ή οι καταστάσεις της συνιστώσας των πράξεων [του αυτόματου πράξεων (operation automaton)] στο μοντέλο του Γκλουσκόφ για το υπολογιστικό σύστημα). Οι συνθήκες είναι μοναδιαία μερικά κατηγορήματα (unary partial predicates) που ορίζονται από το σύνολο των καταστάσεων δεδομένων. Οι προτασιακές συνδέσεις (propositional connectives) ορίζονται στην άλγεβρα των συνθηκών και λειτουργούν όπως στην προτασιακή άλγεβρα Kleene (η λογική διάζευξη και σύζευξη ορίζονται ασθενέστερα ώστε να διατηρηθεί η μονοτονικότητα). Η εσωτερική πράξη της άλγεβρας των τελεστών είναι ο πολλαπλασιασμός ημι-ομάδων και οι δύο εξωτερικές πράξεις που συνδέουν την άλγεβρα των τελεστών με την άλγεβρα των συνθηκών είναι η υπό συνθήκη επιλογή και η υπό συνθήκη επανάληψη. Τέλος, ο πολλαπλασιασμός ενός τελεστή με μια συνθήκη ήταν μια πραγματική ανακάλυψη: η έκφραση  είναι αληθής αν το  είναι αληθές μετά την εφαρμογή του τελεστή  (σημειώστε ότι η χρονική λογική [temporal logic] στην οποία ανήκει αυτή η πράξη ήταν ακόμα μόνο στα σπάργανά της). Μια τέτοια πράξη επέτρεψε την απόδειξη του ακόλουθου θεωρήματος ανάλυσης: κάθε πρόγραμμα με τελεστές goto μπορεί να αναπαρασταθεί σε κανονική μορφή, π.χ. ως τελεστής μιας άλγεβρας αλγορίθμων με το ίδιο περιβάλλον πληροφορίας και γενικούς τελεστές και συνθήκες.

Οι K. L. Yushchenko και G. E. Tseitlin συνέβαλαν σημαντικά στην ανάπτυξη της άλγεβρας των αλγορίθμων και στην εφαρμογή της στην αυτοματοποίηση και τη σχεδίαση συστημάτων λογισμικού που βασίζονται σε τυπικούς μετασχηματισμούς. Η μονογραφία τους «Άλγεβρα. Γλώσσες. Προγραμματισμός» γραμμένη μαζί με τον Γκλουσκόφ ανατυπώθηκε πολλές φορές και μεταφράστηκε στο εξωτερικό.

Οι αλγεβρικές μέθοδοι και ιδέες του Γκλουσκόφ έχουν αναπτυχθεί δημιουργικά. Αυτές οι ιδέες χρησιμοποιήθηκαν επιτυχώς στην επαλήθευση και τη βελτιστοποίηση λογισμικού, τον προγραμματισμό με περιορισμούς (constraint programming), τη σχεδίαση των συσκευών υλικού υπολογιστών κ.λπ.

Η εμφάνιση της παράλληλης και κατανεμημένης υπολογιστικής (parallel and distributed computing) στα τέλη του 20ού αι. κατέστησε αναγκαία την ανάπτυξη μεθόδων ανάλυσης τέτοιων υπολογισμών, επειδή δε μπορούσαν να εφαρμοστούν οι διαθέσιμες μέθοδοι ανάλυσης ακολουθιακών υπολογισμών. Αυτό οδήγησε στην εμφάνιση νέων μαθηματικών μοντέλων: συγχρονισμένα (timed) και υβριδικά αυτόματα, απλά, συγχρονισμένα και υβριδικά δίκτυα Petri (Petri nets), συστήματα μετάβασης (transition systems) και τις παραλλαγές τους. Η μελέτη των ιδιοτήτων τους απαιτούσε νέες μεθόδους ανάλυσης όπως η επίλυση γραμμικών Διοφαντικών περιορισμών σε διακριτά πεδία [linear Diophantine constraints over discrete domains] (το πεδίο Boolean {0, 1}, το σύνολο των φυσικών αριθμών, το σύνολο των ακεραίων, τα πεπερασμένα πεδία και δακτύλιοι).

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

Οι ιδέες του Γκλουσκόφ για τη δημιουργία της τεχνητής νοημοσύνης ώθησαν στην περαιτέρω ανάπτυξη των αλγεβρικών μεθόδων σε πολύ διαφορετικά πεδία των [τυπικο-]λογικών γλωσσών. Συγκεκριμένα, η αυτοματοποιημένη αναζήτηση αποδείξεων θεωρημάτων στις γλώσσες κατηγορηματικής λογικής πρώτης τάξης με ισότητα (first-order predicate languages) ανέδειξε το ζήτημα της ενοποίησης της έκφρασης αυτών των γλωσσών. Το πρόβλημα της ενοποίησης (unification) είναι πρόβλημα επίλυσης εξισώσεων στην αντίστοιχη θεωρία εξισώσεων, που απαιτεί την ανάπτυξη αλγορίθμων για την επίλυση αυτών των εξισώσεων με καθαρά αλγεβρικές μεθόδους. Οι μελέτες σ’ αυτή την περιοχή οδήγησαν σε μια πιο λεπτομερή ανάλυση και καθιέρωση νέων αλγοριθμικών ιδιοτήτων ήδη γνωστών τύπων άλγεβρας.

Η K. L. Yushchenko και η σχολή της

Η σχολή θεωρητικού προγραμματισμού που ιδρύθηκε από την Yushchenko αναπτύχθηκε σε στενή συνεργασία με τη σχολή του Γκλουσκόφ. Όπως η Ada Lovelace ήταν η πρώτη προγραμματίστρια της αναλυτικής μηχανής Babbage, η Kateryna Lohvynivna Yushchenko ήταν η πρώτη γυναίκα που έγραψε προγράμματα για τον υπολογιστή MEOM (MESM), τον πρώτο ηλεκτρονικό υπολογιστή στην ευρωπαϊκή ήπειρο. Συγκεντρώνοντας και κατανοώντας την εμπειρία του προγραμματισμού σ’ αυτόν τον υπολογιστή έφτασε στα πρώτα μαθηματικά αποτελέσματα στη θεωρία του προγραμματισμού: η μέθοδος του τελεστή Lyapunov και η γλώσσα προγραμματισμού Address αναπτύχθηκαν από την K. L. Yushchenko και τον V. S. Korolyuk.

Ήδη από το 1956, οι δημιουργοί τη γλώσσας Address σωστά αναγνώρισαν τις βασικές αρχές των αλγοριθμικών γλωσσών προγραμματισμού: τη χρήση μαθηματικών τύπων και του τελεστή ανάθεσης [τιμών]. Αλλά η κεντρική ιδέα ήταν η ρητή διάκριση μεταξύ της διεύθυνσης και του περιεχομένου της. Έτσι, εφευρέθηκε η τεχνική της χρήσης δεικτών [pointers], που κυριάρχησε και θεωρητικά γειώθηκε στη θεωρία και πρακτική του προγραμματισμού στη Δύση πολύ αργότερα και χρησιμοποιείται ευρέως πρακτικά στο σύγχρονο προγραμματισμό, όπως στη γλώσσα C. Η αφοσίωση στις διευθύνσεις υψηλού επιπέδου (high-rank addresses) οδήγησε στις τότε αρχικές μεθόδους προγραμματισμού για [τυπικο-]λογικά προβλήματα (μη αριθμητικά, όπως τα έλεγαν).

Στις αρχές της δεκαετίας του 1960, δημιουργήθηκαν οι πρώτοι μεταγλωττιστές [compilers] για τη γλώσσα Address. Αλλά αυτή η γλώσσα δημιουργήθηκε σε απομόνωση από τη διεθνή κοινότητα, που ήδη είχε διανοηθεί τις Algol και Fortran. Αν η επικοινωνία μεταξύ των επιστημόνων ήταν στενότερη, η γλώσσα Address μπορούσε να είναι μια από τις πρώτες γλώσσες προγραμματισμού διαδεδομένη παγκόσμια. Καθώς αυτό δεν έγινε, πήραμε έτοιμες τις Algol, Fortran και Lisp και η ομάδα της Yushchenko, που αργότερα εξελίχθηκε σε μια από τις διασημότερες σχολές προγραμματισμού στη Σοβιετική Ένωση, μετατοπίστηκε στην ανάπτυξη μεταγλωττιστών για τις συμβατικές γλώσσες και την ανάλυση θεωρητικών προβλημάτων.

Υπολογισμοί τύπου μακρομεταφορέα (macroconveyor computations)[2]

Στα τέλη της δεκαετίας του 1970 και τις αρχές της δεκαετίας του 1980, ξεκίνησε η δουλειά πάνω σε νέες αρχιτεκτονικές υπερυπολογιστών πολυεπεξεργαστών (multiprocessor supercomputer architectures) ακολουθώντας τις ιδέες του Γκλουσκόφ. Αρχικά, υπήρξε η ιδέα του αναδρομικού υπολογιστή που σχετιζόταν με την αναθεώρηση της αντίληψης του von Neumann. Αυτή η ιδέα παρουσιάστηκε από τον Γκλουσκόφ και τους συνεργάτες του στο Παγκόσμιο Συνέδριο της IFIP[3] στη Στοκχόλμη το 1974 και αργότερα μετασχηματίστηκε στην πιο εφαρμόσιμη ιδέα του υπολογιστικού συστήματος τύπου μακρομεταφορέα. Αυτή η ιδέα εφαρμόστηκε υπό την καθοδήγηση του V. S. Mikhalevich τη δεκαετία του 1980, μετά το θάνατο του Γκλουσκόφ [1982]. Δημιουργήθηκαν τα βιομηχανικά σχέδια του υπερυπολογιστή τύπου μακρομεταφορέα ES-2701, του πρώτου υπολογιστικού συστήματος πολυεπεξεργαστών με κατανεμημένη μνήμη και υψηλή απόδοση παραλληλοποίησης των διεργασιών επίλυσης προβλημάτων. Επιλύθηκαν πολλά επιστημονικά, οικονομικά προβλήματα και προβλήματα βελτιστοποίησης με ρεκόρ ύψιστης απόδοσης. Επιτεύχθηκε απόδοση 500 Mflops[4] που ήταν ρεκόρ για τους υπερυπολογιστές εκείνης της εποχής.

Η επιτυχία του έργου οφειλόταν στη συγκέντρωση μιας ισχυρής ομάδας διάφορων ειδικοτήτων για την εφαρμογή του (μηχανικών, μαθηματικών ειδικευμένων στα συστήματα, προγραμματιστών, ειδικών στις περιοχές των εφαρμογών). Πολλοί συμμετέχοντες είχαν αποκτήσει εμπειρία από την ανάπτυξη των υπολογιστών MIR. Η εφαρμογή του σχεδίου για το υπολογιστικό σύστημα μακρομεταφορέα, προϋπέθετε την επινόηση νέων μεθόδων και τεχνολογιών, την παραλληλοποίηση των διαδικασιών επίλυσης προβλημάτων για υπολογιστικά συστήματα με νέα αρχιτεκτονική [που υλοποιούν-υπολογίζουν τις παράλληλες αυτές διαδικασίες], που περιλάμβαναν πολλούς επεξεργαστές και επέτρεπαν [υποστήριζαν] λειτουργία με μεγάλες ποσότητες κατανεμημένων δεδομένων. Σ’ αυτό συνέβαλε σημαντικά η γόνιμη συνεργασία μαθηματικών ειδικευμένων στα εφαρμοσμένα μαθηματικά και τα μαθηματικά συστημάτων. Π.χ., η μελέτη της εφαρμογής του μακρομεταφορέα στην ανάλυση πεπερασμένων στοιχείων της κατάστασης καταπόνησης (stress–strain state) ενός αεροσκάφους, που προτάθηκε από τον V. S. Deineka, συνέβαλε στην εφεύρεση νέων σχεδίων υπολογισμού (computation schemes) και ανταλλαγής δεδομένων στην κατανεμημένη μνήμη. Η ανακάλυψη νέων σχεδίων υπολογισμού για την επίλυση διακριτών προβλημάτων βελτιστοποίησης είχε επίσης μεγάλη επιρροή στην ανάπτυξη των θεωρητικών θεμελίων του προγραμματισμού μακρομεταφορέα (macroconveyor programming).

Η δημιουργία ενός συστήματος λογισμικού για τα υπολογιστικά συστήματα μακρομεταφορέα, που περιλαμβάνει τη γλώσσα παράλληλου προγραμματισμού MAYAK και το λειτουργικό σύστημα για σύστημα πολυεπεξεργαστών με κατανεμημένη μνήμη, ήταν ένα σημαντικό βήμα στην ανάπτυξη των τεχνολογιών παράλληλου προγραμματισμού. Οι αλγεβρικές μέθοδοι με αυτόματα και τα μοντέλα κατανεμημένης υπολογιστικής (distributed computing) ήταν η θεωρητική βάση γι’ αυτή την ανάπτυξη. Επέτρεψαν τη δημιουργία νέων μεθόδων παραλληλοποίησης [διεργασιών] αλγορίθμων και προγραμμάτων και έβαλαν τα θεμέλια για μια νέα προωθημένη τεχνολογία επίλυσης προβλημάτων. Η τεχνική των περιοδικά ορισμένων μετασχηματισμών αποδείχτηκε κατάλληλη όχι μόνο για τη μοντελοποίηση [μαθηματικοποίηση] των υπολογιστικών συστημάτων σε επίπεδο υλικού και υλικολογισμικού (firmware)[5], αλλά και στο επίπεδο του καθορισμού των μετασχηματισμών των δομών δεδομένων στα συστήματα πολυεπεξεργαστών. Η άλγεβρα των δομών δεδομένων που αναπτύχθηκε γι’ αυτό το σκοπό έγινε το κύριο μέσο σχεδίασης αποτελεσματικών προγραμμάτων για υπολογιστές πολυεπεξεργαστών με κατανεμημένη πολυεπίπεδη μνήμη.

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

Ένα από τα επόμενα βήματα στην ανάπτυξη της θεωρίας της υπολογιστικής μακρομεταφορέα είναι η χρήση της αλγεβρικής-δυναμικής προσέγγισης για την κατασκευή παράλληλων προγραμμάτων, η οποία θεωρεί το παράλληλο πρόγραμμα, αφενός, ως μια αλγεβρική έκφραση που υποβάλλεται σε τυπικούς μετασχηματισμούς και, αφετέρου, ως ένα λειτουργικό σημασιολογικό μοντέλο (operational semantic model) στη μορφή μεταβατικού (δυναμικού) συστήματος που αντανακλά το πλήρες δυναμικό της παραλληλίας (parallelism) των λειτουργιών για ένα δοσμένο επίπεδο της περιγραφής ενός μοντέλου. Το σύνολο των αλγεβρικών δυναμικών μοντέλων αναπτύχθηκε ώστε να εξυπηρετεί ένα σύνολο διαφορετικών πτυχών των ταυτοχρονιστικών (concurrency) μοντέλων [ή μοντέλων ταυτοχρονισμού] των συστημάτων πολυεπεξεργαστών, συγκεκριμένα: πτυχές αλγορίθμων, προγράμματος και συντονισμού. Αυτή η προσέγγιση επιτρέπει είτε την ολοκλήρωση της ανάλυσης των πληροφοριών των τελεστών του προγράμματος σε λειτουργική σημασιολογία (operational semantics) των γλωσσών παράλληλου προγραμματισμού και την εφαρμογή της ιδέας του ασύγχρονου υπολογισμού (asynchronous computation) σε επίπεδο συνιστωσών, είτε την έκφραση της αποκτημένης πληροφορίας στο μέρος συντονισμού του μοντέλου και την εφαρμογή του εν δυνάμει ασυγχρονισμού των υπολογισμών στο επίπεδο των αλληλεπιδράσεων μεταξύ συνιστωσών. Στην πρώτη περίπτωση, για ένα δοσμένο βάθος πληροφοριακής ανάλυσης, είναι δυνατή η παραγωγή οικογενειών δυναμικών μοντέλων προγραμμάτων που προσαρμόζονται στις δυνατότητες εφαρμογής και έτσι στα παράλληλα προγράμματα με βελτιωμένη υπολογιστική αποτελεσματικότητα. Σα σύνοδη συνέπεια, κάνει δυνατή την αυτόματη ανάλυση ορισμένων κατηγοριών επικοινωνιακών αδιεξόδων. Στη δεύτερη περίπτωση, τα αποτελέσματα της πληροφοριακής ανάλυσης μπορούν να εκφραστούν στη μορφή των μέσων συντονισμού και να βελτιωθεί σημαντικά την ποιότητα των μηχανισμών συγχρονισμού και ανταλλαγής δεδομένων και μπορεί επίσης να χρησιμοποιηθεί η ανάπτυξη της τυποποίησης [του φορμαλισμού] για την αυτοματοποίηση των μετασχηματισμών του προγράμματος προκειμένου να ελαχιστοποιηθεί η απώλεια αποτελεσματικότητας στην παραλληλοποίηση που προκαλείται από διαφορές στην απόδοση των διαφορετικών επιπέδων της μνήμης του συστήματος πολυεπεξεργαστών. Μια σημαντική συνέπεια της εφαρμογής αυτών των μεθόδων είναι η διεύρυνση των παραμέτρων του επεξεργαστή, όπου η επιτάχυνση των υπολογισμών επιτυγχάνεται από τη γραμμική εξάρτηση του παράλληλου προγράμματος από τον αριθμό των επεξεργαστών που εκτελούν το πρόγραμμα αυτό.

Οι μελέτες των δεκαετιών 1970-1980 στην ανάπτυξη αλγεβρικών μοντέλων με αυτόματα και των εφαρμογών τους στην επίλυση συγκεκριμένων προβλημάτων της τεχνολογίας λογισμικού και υλικού είχε σαν αποτέλεσμα τη μονογραφία «Μαθηματική Θεωρία της Σχεδίασης Υπολογιστικών Συστημάτων» από τους Kapitonova και Letichevskii. Η έννοια του διακριτού δυναμικού συστήματος, π.χ. σύστημα μετάβασης με μη επισημασμένες μεταβάσεις (nonlabeled transitions), πάρθηκε ως βασικό μοντέλο του υπολογιστικού συστήματος σ’ αυτή τη μονογραφία. Έδειξε πόσο λεπτομερώς και εμπλουτισμένα αυτό το μοντέλο μπορεί να χρησιμοποιηθεί για να παρθούν οι βασικές έννοιες και αποτελέσματα της θεωρίας των αφηρημένων και δομικών αυτόματων και της θεωρίας σχεδίων προγραμμάτων, μοντέλα για συστήματα πολυεπεξεργαστών και οι βασικές δομές για τη δημιουργία παράλληλων εφαρμογών. Επίσης έδειξε πώς γίνεται το πέρασμα από τις προδιαγραφές του συστήματος στην υλοποίησή του, πώς εκτελούνται μετασχηματισμοί ισοδύναμων υπολογιστικών συστημάτων κ.λπ.

Η θεωρία διακριτών επεξεργαστών και σχέδια προγραμμάτων

Λίγο μετά την εμφάνιση του μοντέλου των αλληλεπιδρώντων αυτόματων του Γκλουσκόφ ως βασικού μοντέλου υπολογιστή, έγινε εμφανές ότι είναι κατάλληλο και για τη δημιουργία μοντέλων λογισμικού. Αυτό το μοντέλο σχετιζόταν με τη θεωρία σχεδίων προγραμμάτων και αναπτύχθηκαν οι προσεγγίσεις για τη λύση του προβλήματος της ισοδυναμίας προγραμμάτων και τυπικών μετασχηματισμών προγραμμάτων.

Με δεδομένο ότι το πρόβλημα της ισοδυναμίας διακριτών επεξεργαστών είναι αλγοριθμικά μη επιλύσιμο, μελετήθηκαν διάφορες αφαιρέσεις του βασικού μοντέλου. Το μοντέλο διακριτού επεξεργαστή πάνω σε ημι-ομάδες και ομάδες έγινε το πιο δημοφιλές. Οι εκπρόσωποι της σχολής του Γκλουσκόφ κατάφεραν πολλά αποτελέσματα πάνω στην επιλυσιμότητα του προβλήματος της ισοδυναμίας [προγραμμάτων και τυπικών μετασχηματισμών προγραμμάτων]. Αυτά τα αποτελέσματα είχαν σημαντική επιρροή στην έρευνα στις σχολές θεωρητικού προγραμματισμού στο Novosibirsk, τη Μόσχα και την Αμερική.

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

Σημειώσεις

[1] Στην πληροφορική καλούμε προστακτικό προγραμματισμό, σε αντίθεση με το δηλωτικό προγραμματισμό, ένα προγραμματιστικό υπόδειγμα όπου το ζητούμενο κατασκευάζεται/υπολογίζεται αλλάζοντας την κατάσταση του υπολογιστή μέσω εντολών. Η ιδέα είναι ότι έχουμε εντολές (statements) που συνήθως μοιράζονται κοινές μεταβλητές. Το υπόδειγμα αυτό ακολουθούν οι διαδικαστικές γλώσσες προγραμματισμού, όπως η Pascal, η C, η Fortran, κ.ά., αλλά και πολλές αντικειμενοστραφείς γλώσσες όπως η Java, η C++, η C#, κ.ά. Η ιδέα του προστακτικού προγραμματισμού απορρέει από την αρχιτεκτονική von Neumann η οποία σχεδιάστηκε την δεκαετία 1940. Κατά την αρχιτεκτονική αυτή η κάθε εντολή (γλώσσας μηχανής) εκτελείται διαδοχικά (σε κάθε κύκλο λειτουργίας του επεξεργαστή). Η μετέπειτα ανάπτυξη των γλωσσών προγραμματισμού υψηλού επιπέδου (όπως για παράδειγμα η Pascal ή η C) βασίστηκαν στην αρχιτεκτονική von Neumann και υλοποίησαν το υπόδειγμα του προστατικού προγραμματισμό όπου ο προγραμματισμός γίνεται σε γλώσσα υψηλού επιπέδου.

[2] Με όρους ταξινόμησης που χρησιμοποιούνται σήμερα, με κριτήριο τον αριθμό των ροών εντολών και τον αριθμό των ροών δεδομένων, η αρχιτεκτονική μακρομεταφορέα (macroconveyor) κατατάσσεται στην κατηγορία MIMD (Multiple Instruction Streams, Multiple Data Streams – πολλαπλές ροές εντολών, πολλαπλές ροές δεδομένων).

[3] International Federation of Information Processing (IFIP – Διεθνής Ομοσπονδία Επεξεργασίας Πληροφοριών).

[4] Τα FLOPS (Floating-point Operations per Second) ή Flop/s, δηλαδή ο αριθμός πράξεων κινητής υποδιαστολής ανά δευτερόλεπτο, είναι μια μετρική της απόδοσης των ηλεκτρονικών υπολογιστών. Πρόκειται για ένα είδος μονάδας μέτρησης της ταχύτητας, που βασίζεται στο πόσες πράξεις κινητής υποδιαστολής μπορεί να εκτελέσει ο υπολογιστής σε ένα δευτερόλεπτο.

[5] Λογισμικό σε γλώσσα μηχανής, κατάλληλο μόνο για το συγκεκριμένο μοντέλο-τύπο υλικού.