Παράλληλα συστήματα λογικού προγραμματισμού με υποστήριξη περιορισμών

Abstract

Logic programming (LP) maintains all the advantages of the declarative programming paradigm, and the main disadvantage of reduced efficiency. To this problem two "orthogonal" solutions have been proposed. The first concerns exploitation of the parallelism that is naturally embedded in logic programs. The second concerns replacing the standard unification process of LP with constraint solving, a solution that led to the introduction of constraint logic programming (CLP). The above two solutions are orthogonal in the sense that they can exist simultaneously in a system, thus leading to the creation of parallel constraint logic programming systems. The present thesis is an effort to propose a solution to the open problem of implementing such systems. In this framework the research described in this thesis was aimed toward a complete solution to the problem of increasing the efficiency of CLP programs, by proposing both a platform, CSPCONS, for the implementation of parallel/distributed CLP applications and a parallel consistency algorithm Dis-SAC. CSPCONS supports programming based on communicating sequential processes that interact through message passing and event generation. Communication between processes is naturally extended over TCP/IP channels, thus allowing the parallel execution of CLP programs in low cost multi-processor environments. CSPCONS is the first LP platform that combines constraint solving, processes and channel based communication and is an excellent platform for the prototyping and implementing parallel/distributed CLP applications. In the present work, this was further demonstrated by the development of two example applications: a distributed workforce management application and an animator tool for X-machines. Towards the more efficient execution of CLP programs, the distributed filtering algorithm Dis-SAC was proposed. Dis-SAC is a consistency algorithm that presents important characteristics, such as the fact that it imposes a high degree of consistency, simple implementation and linear speedup with respect to the number of processing units involved in the execution. The combination of CSPCONS and the Dis-SAC algorithm for the solution of CLP problems, proved to be highly efficient, as demonstrated by the initial implementation and experimental results. This combination is the main result of the present research effort: a complete solution to the efficient execution of CLP programs in a multi-processor environment.

Ο λογικός προγραμματισμός (LP) διατηρεί όλα τα πλεονεκτήματα του δηλωτικού προγραμματισμού, με βασικό μειονέκτημα τη μειωμένη απόδοση. Για την επίλυση αυτού του προβλήματος προτάθηκαν δύο λύσεις: η εκμετάλλευση του παραλληλισμού και η αντικατάσταση της διαδικασίας ενοποίησης με επίλυση περιορισμών (LP με υποστήριξη περιορισμών-CLP). Οι δύο λύσεις είναι ορθογώνιες, δηλαδή είναι δυνατή η ταυτόχρονη εκμετάλλευση τους σε ένα σύστημα, οδηγώντας έτσι στα παράλληλα συστήματα λογικού προγραμματισμού με υποστήριξη περιορισμών. Η διατριβή προτείνει μια λύση στο ανοικτό πρόβλημα της υλοποίησης τέτοιων συστημάτων. Στο πλαίσιο αυτό, η ερευνητική εργασία έγινε στην κατεύθυνση εύρεσης μιας ολοκληρωμένης λύσης για την αύξηση της απόδοσης προγραμμάτων CLP, προτείνοντας τόσο μια πλατφόρμα, την CSPCONS, κατάλληλη για την ανάπτυξη παράλληλων/κατανεμημένων CLP εφαρμογών, καθώς και ενός παράλληλου αλγορίθμου εξασφάλισης συνέπειας σε προβλήματα περιορισμών, του Dis-SAC. Η CSPCONS υποστηρίζει προγραμματισμό βασισμένο σε σειριακές διεργασίες που επικοινωνούν μέσω καναλιών και συμβάντων. Η επικοινωνία μεταξύ των διεργασιών επεκτείνεται με φυσικό τρόπο πάνω από TCP/IP δίκτυα, επιτρέποντας έτσι την παράλληλη εκτέλεση CLP προγραμμάτων σε πολυεπεξεργαστικά περιβάλλοντα χαμηλού κόστους. H CSPCONS αποτελεί την πρώτη πλατφόρμα LP που συνδυάζει ικανοποίηση περιορισμών, διεργασίες και επικοινωνία μέσω καναλιών και αποτελεί μια εξαιρετική πλατφόρμα για προτυποποίηση και ανάπτυξη κατανεμημένων/παράλληλων CLP εφαρμογών. Η καταλληλότητα της πλατφόρμας καταδεικνύεται στα πλαίσια της παρούσας έρευνας με την ανάπτυξη δύο εφαρμογών: μιας κατανεμημένης εφαρμογής διαχείρισης προσωπικού και ενός εργαλείου απεικόνισης εκτέλεσης Χ-μηχανών. Στην κατεύθυνση της αποδοτικής επίλυσης προβλημάτων CSP προτάθηκε επίσης ο κατανεμημένος αλγόριθμος διήθησης τιμών Dis-SAC. Ο Dis-SAC ανήκει στην κατηγορία των αλγορίθμων συνέπειας CSP προβλημάτων και παρουσιάζει σημαντικά χαρακτηριστικά, όπως είναι το γεγονός ότι εξασφαλίζει ισχυρή συνέπεια, απλότητα στην υλοποίηση, καθώς και γραμμική αύξηση της απόδοσης του σε σχέση με τον αριθμό των επεξεργαστών. Ο συνδυασμός της CSPCONS και του αλγορίθμου Dis-SAC για την επίλυση προβλημάτων αποδείχθηκε ιδιαίτερα αποδοτικός, όπως φάνηκε από την αρχική υλοποίηση και πειραματική μελέτη. Ο συνδυασμός των δύο αποτελεί και το κύριο αποτέλεσμα της παρούσας ερευνητικής εργασίας: μια ολοκληρωμένη λύση για την αποδοτική εκτέλεση προγραμμάτων CLP σε πολυεπεξεργαστικά περιβάλλοντα.